Ahh... Starting to make a believer out of you... :)

The really odd thing is that I can do a locate on an indexed field I already have set (which should be cached) and it's still slow.

No, I haven't indexed on Deleted().

The tables are all opened in Share mode, but nothing was being added to the tables during any of the tests. Also, I think it is important to stress that I was working with tables of 10 million records+. I didn't notice it on even fairly large tables, but when you start working with millions of records it becomes more obvious.