I assume your index design is a problem. You have a CLUSTERED index in the DATETIME field, and I suspect that this is not unique data like VarId, and therefore you did not declare it as UNIQUE. Since it is not unique, there is a hidden 4-byte "uniqueifier" field (so that each row can be physically unique, regardless of what you give it unique data), and rows with the same DATETIME value are essentially random in the group same DATETIME value (therefore, even narrowing the time still requires scanning through this grouping). You also have a NONCLUSTERED index for VarId, Timestamp. Non-NONCLUSTERED indexes include data from the CLUSTERED index, so your NONCLUSTERED index is actually valid: VarId, Timestamp, Timestamp (from the CLUSTERED index). That way, you could leave the Timestamp column in the NONCLUSTERED index, and everything would be the same with the optimizer, but in a sense, it would be better, since it would be a smaller index.
Thus, your physical layout is based on a date, while VarId values propagate along those dates. Consequently, VarId = 135 can propagate very far from each other over data pages. Yes, your nonclustered index merges them together, but the optimizer probably looks at the fact that you need all the fields (the "SELECT *" part) and Timestamp <'2012-06-01 14:21:00' in addition to which seems to get most of what you need, rather than searching a few lines and doing a bookmark search to get the "Value" field to do "SELECT *". It is possible that if you simply "SELECT TOP (1) VarId, Timestamp", most likely use your NONCLUSTERED index without the need for the hint "INDEX =".
Another issue affecting overall performance may be that ORDER BY is querying the timestamp in DESC order, and if you have a CLUSTERED index in ASC order, this will be the opposite direction of what you are looking for (at least in this request). Of course, in this case, then it would be normal to have a timestamp in the NONCLUSTERED index if it was in DESC order.
My advice is to rethink the CLUSTERED index. Judging by this request alone (other requests / uses may change the recommendation), try resetting the NONCLUSTERED index and re-creating the CLUSTERED index with the Timestamp field first, in DESC order, as well as with VarId so that it can be released by UNIQUE. So:
CREATE UNIQUE CLUSTERED INDEX [UIX_Archive_Timestamp_VarId] ON Archive (Timestamp DESC, VarId ASC)
This, of course, suggests that the combination of Timestamp and VarId is unique. If not, then try to do this without the UNIQUE keyword.
Update:
To bring all this information and tips together:
When developing indexes, you need to consider the distribution of data and use cases for interacting with it. Most often there is a LOT to consider, and several different approaches will seem good in theory. You need to try several approaches, profile / check them and see which ones work best in reality. There is no “always do this” approach, not knowing all aspects of what you are doing, what else is going on, and what else you plan to use and / or modify this table, which I suspect was not presented in the original question .
So, to start the journey, you order records by date and look at date and date ranges, of course, in order to put Timestamp in the first place more than you do, and has less fragmentation, especially if it is defined as DESC in CREATE. If the NC index on just VarId at that point would be good, even if it spreads, to view the rowset for a specific VarId. So maybe start there (reverse the direction of the CLUSTERED index and remove the timestamp from the NC index). See how these changes compare with the existing structure. Then try moving the VarId field to the CLUSTERED index and delete the NC index. You say that the combination is also not unique, but increases the predictability of string ordering. See how it works. Is this table updated? If not, and if the Value field along with Timestamp and VarId is unique, try adding it to the CLUSTERED index and be sure to create it using the UNIQUE keyword. See how these different approaches work by looking at the actual execution plan and using SET STATISTICS IO ON before running the query and see how logical reading compares between the different approaches.
Hope this helps :)