Thanks Satish,

1) Statistics were up to date, but I updated them again with FULLSCAN and there was no difference.

2) Indexes have less than 1% fragmentation so it's not that

3) The query plan is very simple - just a Clustered Index Seek

We are talking really basic queries like SELECT c1, c2, c3, c4, c5 FROM table WHERE id=1

4) I upped the compatibility level to 100 and that made no difference.