I've run into this same problem many times, myself.

Remember: the plan that gets cached is the result of the first call to the stored proc. In our system, we have both large and small customers (data wise). If a smaller customer is the first one to call the proc, it will be optimized to handle the smaller data returns, which trashes performance for the larger customers.

I've seen procs that run in <1 sec jump to 8 secs if the plan is a bad one, but query analyzer will still run it in 1 sec. Not sure why you end up with 2 different plans based on login, but somehow it does.

In our case, I just added the WITH RECOMPILE option to the stored proc in question (only 1 was really causing this problem), and it has since prevented it from showing back up again.

IMHO, the smaller hit for the recompile based on the current parameters is much less than relying on the initial call to generate the best plan for both large and small data sets.

Just my $0.02 input on this sometimes very annoying issue.