I dont know the full story or what markslinks was, but I would say that you have 2 courses of action here.
1) Report the domain as having incorrect whois. Thats not a valid UK postcode or telephone/fax number and is technically a breach of the registration agreement.
2) Go after the registrar, especially if the renewal was paid. It would appear that they *may* operate a similar system to another well known registrar whereby if renewals arent paid, they go into a pool for their subscribers before they actually go through the full deletion process (the giveaway is the domain creation date). If they have made an error then they should be able to reassign it to you. I know that the other registrar can do this as it has happened to me in the past.
Of course if I have totally missed the point on all this then just ignore all of the above
