Looks like (bad) parameter sniffing in action.

Grant Fritchey wrote an excellent chapter of SQL Server MVP Deep Dives Vol. 2[/url] all about parameter sniffing and I strongly suggest buying this book. It's a conference in a book. Worth every penny.

Without seeing your code I can't get into details, but looks like the optimizer takes a different path when executing the statement ad-hoc and in a stored procedure. This is something that can definitely happen when bad parameter sniffing kicks in. As to why updating statistics affects the two plans in a different way, I would separate the two issues:

1) statistics are outdated

2) bad parameter sniffing occurs

The parameter sniffing issue is not caused by outdated statistics: it gets worse with stale statistics, but doesn't go away completely when stats are up to date.

However, the fix is easy for both issues:

For the first one, update your stats.

For the second one, you could use local variables or the OPTIMIZE FOR hint.

Hope this helps

Gianluca