They are running sql server 2008r2 standard edition, though the quicker performer is at sp1, the slower at sp2.

Yes it takes a very long time to compile, once I had run it in it once, I could rerun it quickly, but it doesn't seem to stay in the cache (need to verify this tomorrow), and this behaviour is different to the other server, takes no time for the initial compile (certainly not 10 minutes anyway).

The application seems to run these queries rather than them being wrapped in stored procedures, but the execution syntax should be the same each time.

I did update the stats earlier as I noticed the estimated rows was different to actual.

The DDL is pretty much the same (though there are a few extra views in live not relevant to the query), i ran sql compare to verify this earlier today. Indexes should be the same, if anything the slower of the two servers has less fragmentation as I rebuild the indexes today.