Great!! Recently one of the stored procedure was behaving some what in the similar way as mentioned, I did use sp_recompile which made it much faster, but didnt knew the reason behind..!!

The Great article for explaning the behaviour of sp..!!