I'm in the US, not the UK, so I'm not sure how helpful this will be, but I use:
http://www.uspto.gov/main/profiles/acadres.htmto search for registered trademarks.
I did a little research on the subject a while back. There are registered trademarks ("R in a circle") which, as the name suggests, requires registering with the government. This takes time (for a search to make sure no one else has the same trademark) and money (regardless of how the search turns out) but provides the best protection.
Then there are unregistered trademarks ("TM"). Anyone can use this protection, either on its own or while waiting to get a registered trademark in effect. It's not as protective, however. Its main use seems to be protecting local business at the state level, so that no one else in your state can have the same sort of walk-in business with the same name as yours. On the national level, about all it does is establish "prior use" so that if you've been selling a product for years with a given name and someone new starts selling the same sort of product with the same name, you can take them to court to force a change (though that naturally costs money and isn't a sure thing).
One other thing to consider is that different products can legally share the same trademarked names if they're different
kinds of products. For example, a search of the database above shows live, registered trademarks for "Harpoon" soft drink, "Harpoon" aquatic herbicide, and "Harpoon" orthopedic implant among others. So, even if the name that you want is trademarked, if its not trademarked for a game then you'll likely be able to use it for yours (as GDW did for their naval wargame).
I say "likely" because I've read the story of an Avalon Hill trivia boardgame that was named "Shakespeare." They were contacted by the holders of the Shakespeare fishing gear trademark and told to change the name (one of the legal requirements of a trademark is that you must challenge any potential infringer or you risk losing the rights to the name). It was resolved, and the game kept the name, when Avalon Hill agreed not to make any fishing gear with that name, and the fishing gear company agreed not to make any games.
Anyway, I agree with chaotic's google suggestion as well. That should be a first step to make sure that no one else is selling a game with the same name.
But there's always a chance that someone is quietly registering it, in which case they'll likely get the rights to it and force you to change the name even with your prior use of "TM" unless you can afford to take them to court. Or maybe you'll get lucky, and they'll buy the name from you. That happened to a local BBS way back, which was named "America Online": when AOL started, they paid the sysop some moderate amount to change his board's name since he'd been using it for years.