Different client results in different excution plan?

This is the second or third time I've run into this issue over the past several years and want to see if anyone else is experiencing it or has a solution....

I have an automated client app that executes a particular SP 5-10k times/day, typically in << 1s.  Saturday and Monday evening, the SP started timing out at the 30 second (connection timeout from the client).  I could make sense of the situation if every execution of the SP resulted in the same execution plan, but executing it from the client app resulted in slow plan and executing from Management Studio resulted in fast plan 40 seconds later.

Troubleshooting:
1.  Updated stats on Transaction Log      Result: No performance change
2.  Killed client app and restarted       Result: No performance change
2.  Restarted client PC and client app      Result: Performance back to normal.

I could probably resolve the symptom by providing an index hint to the SP, but I'm trying not to rewrite 100s of SPs to force execution plans.

Any help would be great!

-- Rob


**** Times out at 30 seconds
StmtText from PC1 app 2008-04-08 17:52:23:590  
--------
Top(TOP EXPRESSION:((1)))
|--Sort(ORDER BY:([STS].[dbo].[TransactionLog].[DatePerformed] DESC))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000]))
|--Nested Loops(Inner Join, OUTER REFERENCES:([STS].[dbo].[TransactionData].[TransactionID], [Expr1015]) OPTIMIZED WITH UNORDERED PREFETCH)
|    |--Compute Scalar(DEFINE:([Expr1012]=CONVERT_IMPLICIT(numeric(18,5),[STS].[dbo].[TransactionData].[DataValue],0)))
|    |    |--Nested Loops(Inner Join, OUTER REFERENCES:([STS].[dbo].[ActionDetails].[DetailID]) OPTIMIZED)
|    |         |--Index Seek(OBJECT:([STS].[dbo].[ActionDetails].[ActionID-DID-Other]), SEEK:([STS].[dbo].[ActionDetails].[DetailName]='RemainingBurnIn') ORDERED FORWARD)
|    |         |--Index Seek(OBJECT:([STS].[dbo].[TransactionData].[DID-Value-TID]), SEEK:([STS].[dbo].[TransactionData].[DetailID]=[STS].[dbo].[ActionDetails].[DetailID])ORDEREDFORWARD)
|    |--Index Seek(OBJECT:([STS].[dbo].[TransactionLog].[TSN-TransactionID]), SEEK:([STS].[dbo].[TransactionLog].[TSN]=[@TSN] AND [STS].[dbo].[TransactionLog].[TransactionID]=[STS].[dbo].[TransactionData].[TransactionID]) ORDERED FORWARD)
|--RID Lookup(OBJECT:([STS].[dbo].[TransactionLog]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)



**** Runs to completion in 19 mS
StmtText from Management Studio on PC2 at 2008-04-07 17:53:13.293      
--------
Top(TOP EXPRESSION:((1)))
|--Nested Loops(Left Semi Join, WHERE:([STS].[dbo].[TransactionData].[DetailID]=[STS].[dbo].[ActionDetails].[DetailID]))
|--Compute Scalar(DEFINE:([Expr1012]=CONVERT_IMPLICIT(numeric(18,5),[STS].[dbo].[TransactionData].[DataValue],0)))
|    |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1004], [Expr1017]) WITH ORDERED PREFETCH)
|         |--Nested Loops(Inner Join, OUTER REFERENCES:([STS].[dbo].[TransactionLog].[TransactionID], [Expr1016]) WITH ORDERED PREFETCH)
|         |    |--Sort(ORDER BY:([STS].[dbo].[TransactionLog].[DatePerformed] DESC))
|         |    |    |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000], [Expr1015]) WITH UNORDERED PREFETCH)
|         |    |         |--Index Seek(OBJECT:([STS].[dbo].[TransactionLog].[TSN]), SEEK:([STS].[dbo].[TransactionLog].[TSN]=[@TSN]) ORDERED FORWARD)
|         |    |         |--RID Lookup(OBJECT:([STS].[dbo].[TransactionLog]), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)
|         |    |--Index Seek(OBJECT:([STS].[dbo].[TransactionData].[TransactionID]), SEEK:([STS].[dbo].[TransactionData].[TransactionID]=[STS].[dbo].[TransactionLog].[TransactionID]) ORDERED FORWARD)
|         |--RID Lookup(OBJECT:([STS].[dbo].[TransactionData]), SEEK:([Bmk1004]=[Bmk1004]) LOOKUP ORDERED FORWARD)
|--Index Seek(OBJECT:([STS].[dbo].[ActionDetails].[ActionID-DID-Other]), SEEK:([STS].[dbo].[ActionDetails].[DetailName]='RemainingBurnIn') ORDERED FORWARD)