Does anyone know the general policy on how soon after expiry a domain name becomes available again to register on the open market?

I ask because a 'whois' enqury on a domain name I have my eye on says that it expired in Feb 2001, and yet if I try to register it, the various services all tell me that the domain name is already registered. Perhaps there's an error with the domain name records...

Thanks.