There are a number of reasons why a domain gets picked up right after expiration. Somebody could have already put a request to buy it. Here's a resource to get you stated on getting domains after they expire.
For what it's worth, I don't believe your situation had anything to do with you having searched for the domain before.
http://www.pixelmade.com/blog/domain-names/how-buy-expired-domain-name