Recently I had this funny query which ignored and index although it seemed very useful to me. Normally I don't question the query optimizer too much but this time I was really sure.
I tried a UPDATE STATISTICS WITH FULLSCAN on the index and all of the sudden my query started to use the index.
Statistics on indexes are always created with fullscan because SQL Server has to scan all of the data anyway. This counts for newly created indexes and reindexing. As far as I can see auto statistics update is always performed by sampling the index or table.
Time for some more testing tomorrow! :-)