As few people have requested it - here's my experience on using various press release distribution services I posted in JohnyZupper's
Pricing Tips thread.
I send lots of press releases both at my job and for my own stuff. I have used most of the popular services. Here's my experience on each:
http://www.gamespress.com/ - a free PR distribution service and source of news for game journalists. It's free to submit your story, so there's no reason not to do it every time you release something. The effects aren't as good as when using a paid service, but still some outlets will pick up your game.
http://www.softpressrelease.com - the most expensive and theoretically the best PR service. In practice, the differences between this and cheaper equivalents are not that big. We used it for the bigger news on our casual games. The effect was slightly better than when using other websites, but I'm not completely convinced that it was worth it - sending a game-related PR is $140, so a bit pricey.
Then again, I only sent news on casual games through them. It might be just that their contacts are more hardcore/general gaming oriented.
Their submission system isn't very convinient, as releases aren't handled automatically - sometimes you have to wait for their employee to contact you and send your stuff.
http://www.gamerelease.net/ - GameProducer.net's PR distribution service. It has one huge advantage - you pay around $100 and can use them as many times as you want for one year. If you plan to make many releases to build up hype or if you expect many updates to your game, they are a very good choice. They will always get you further than a free service and $100 is not that much for an unlimited amount of releases. Their submission system is also very convinient and fully automatic.
http://www.mitorahgames.com/Submit-Game-Press-Release.html - Mitorah games is a small indie company offering to send PRs through their own contact list. I sent the news on one of the MAGI updates through them and the results were great. My traffic was slowly dying back then and two days after the release, I've got a concerned letter from my web host, saying that I suddenly started using too much bandwidth (20GB per day in demo downloads).
However, it might be just that their contacts were perfectly suited for my needs - MAGI is a strategy/rpg and these guys specialize in this kind of games. Still, I recommend them. Even if just to support fellow indies trying to make some extra buck.
The price is very competitive at $60-$85, though there's no automated system there - you have to get in contact with Tero and exchange few emails to get your story out.
http://prmac.com/ - if you plan to release for Mac, I totally recommend these guys. Their submission system is very convinient and handy (the best one I used), the release costs only around $15 and your news are always picked very fast by all the major Mac outlets. They also have excellent customer support and really try to make sure you are satisfied.
In general, sending press releases is always a good idea. Even if you decide to use a free service or just sign up for a year of gamerelease.net, for the little amount of work it takes, it will probably get you more links and visibility than any other form of marketing you can do in so little time. And you always have that chance of finding some journalist really interested in your stuff.
That said, I see a general decline in traffic gotten through PRs. It might be that there's just too many of them or that the magazines are cutting the amount of content they put out at the cost of indie games. As for now, if it isn' something really exciting (like a new game announcement or premiere), we just use
http://www.gamespress.com/ and
http://www.gamerelease.net/.
It's much better with Macs though. Even pretty unsignificant news released through
http://prmac.com/ have some nice effect on our traffic and we try to use them whenever possible.
Hope it helps.