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.