mayurkb I switched parametrization to forced on the offending database, and now when I run the query (after it's initial 10 minute run into the cache), even if I change it slightly by adding/removing spaces it returns in seconds.
This is definitely a problem with the compilation of the query, but what would be causing this extra long compilation time, does compilation utilise CPU heavily? there are 8 cores on the server, but it is a virtual server, see any problems here?
The query takes seconds to compile on the test and current live servers.
Thanks for all your help in this guys, getting me on the right track i think.