I have a feeling that it's bad parameter sniffing - chasing that down now. If nothing comes up there, then I will update stats on all tables EXCEPT the one that I've already updated with no success.