You're on the money with your detective work.

However, I agree with Alex that you should have considered the WITH RECOMPILE option with your create procedure statement.  That's probably in line with your intent.

I'm curious, did you call the sp_recompile on your stored procedure from within the stored procedure itself?

-Larry