Parameter sniffing, or lack thereof. Probably combined with stale statistics so that SQL gets a completely incorrect row estimate when it can sniff the 'parameters' (in this case string literals) while the variables, because they can't be sniffed give a rougher estimate that's not so likely to be affected by stale stats.

http://sqlinthewild.co.za/index.php/2007/11/27/parameter-sniffing/

http://sqlinthewild.co.za/index.php/2008/02/25/parameter-sniffing-pt-2/

Look at the two estimated plans posted (actuals would be far better), look at the row estimations. Without the actual plans there's no way to see which of those estimates are more accurate, but I'll bet that the 5000 is closer than the 1.

p.s. Watch those nolocks. http://blogs.msdn.com/b/davidlean/archive/2009/04/06/sql-server-nolock-hint-other-poor-ideas.aspx