Found another couple suggestions. I hope to try one this weekend myself (depending on time!)http://www.youtube.com/watch?v=AyFMEEV3 ... re=relatedhttp://www.videojug.com/film/how-to-clean-brass
Both involve cleaning solutions, but that's probably what you need to restore badly tarnished items. Again, I am not a fan of chemical treatments myself, but sometimes you can't get away from them. I am also NOT endorsing these solutions (haven't tried them yet even) just offering them as a possibility if you feel you need to try something.
The most interesting one is using tile and grout cleaners. That material is available at most hardware stores. Sure, not as strong as the one in the video but also probably better for more delicate brass anyway!
Have a look and see what you think.