Also could be that the optimizer fixes are enabled/disabled on one of the databases and not the others. That would certainly lead to differences, especially if the query is already a bit on the edge as you describe.
"The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood"
- Theodore Roosevelt
Author of:
SQL Server Execution Plans
SQL Server Query Performance Tuning