Hijacked Registrations...
It is possible that the search from 123-reg is not accessing an updated WhoIs database so is showing names as unregistered, when they already are!!! I know their searches for .uks are correct but maybe their .com's are not!!!
Then again it is possible to monitor searches and register before a user registers. I recently lost five names to someone doing this!! I too was using 123-reg for my searches but also Nominet and another web site that I will not mention.
To view searches you really need server access to the data base being searched, or at least access to the web site back end search program so that you can write to a writeable file to hold the unregistered search results until a time when you can access it and check for good names.
Then again if you knew the layout of the executable file accessing the date base it may be possible to write a program to access this and host it romotely. Anyway all speculation!! I still think it easier to do for somone on the inside.
In my case I think it was either a Nominet employee, 123-reg employee or the owner of the other web site!! I abviously know the name of the person as I can now see them in the WhoIs...
I would be interested in the name of the person who registered your names, can you tell me the first letter of (HIS) surname?