I have a similar problem with a simple 3 table join in a proc which table scans ( to return 1 row ) but if the query is put in QA uses the indexes  12k i/o vs 12 i/o  .  I did loads to the proc and it refused to use the indexes, in the end I dropped the proc and put it back and everthing worked fine - as I say this is a simple query taking 2 int params to return a single row result.

I did all the stuff with the stats including 100% sampling but to no avail - strange!