I'm closing in on a point in the development of my first game that it's ready for Steam Greenlight. I don't even have a name for it though. My project name is Asteroids, but obviously I can't use that. I have a bunch of other ideas, but I'm scared to death of getting sued. Let's use the Edge Vs EA example. Edge Games tried to sue Electronic Arts because they released Mirror's Edge. They were unsuccessful, but the case aside, couldn't EA have just said, "Oops, sorry mates, we'll come up with something else."? I'm developing because I want to secure a real future for my family, but I make $10 an hour busing tables, getting sued would mean financial ruin, right? I barely manage to pay my bills and feed myself, so a Lawyer isn't an option, and there's no other way I know of to be absolutely sure I'm not infringing on someone else's rights.
Changing the name of a larger game development project is often easier said than done because of all the marketing expenses and PR effort which was already invested to promote the old name. Companies like EA run a well-oiled marketing machinery for every title which starts working long before a title is even announced. The money and time they lose through a name-change might far outnumber the cost of the lawsuit. Also, when the game was already sold or the trademark owner feels like the existing marketing has already damaged their brand, the trademark owner could try to demand recourse even when the name is changed immediately.
You can check the US patent office database of registered trademarks to check if your game's name is a trademark registered in the United States. You should also check if there is a database like that specific to your own country.
There is generally no sure way to be completely save from lawsuits because everyone can sue anyone for anything, and finding out if the lawsuit is even remotely justified already takes money from both sides.
I am not a lawyer, but if I would want to protect my private finances from being ruined by a lawsuit against my game, I would consider forming a limited company and distribute my game through that company. A limited company is a separate legal entity from yourself, and when it goes bankrupt you will only lose the money you invested into the company and will not inherit any of its debt. This also means that anyone who sues your company won't see any more money than the company owns, which makes it unattractive for any trademark trolls who don't care about your game and only want money.
But in the long run you should really get proper legal advise and not just rely on what random laypeople on the internet like me tell you. When you want to run a company, legal advise is just part of the cost of doing business.
IANAL. Disclaimer: my advice is based on my experience in the gamedev field alone.
You can not use trademarked names for your actual game. Try and come up with a different name. A lawsuit is an ugly thing.
You can go with something unique-ish like... Kuiper Belt something. Do your best to not even derive your name from other games.