I think we are all in general agreement that this problem started after iOS4 was installed in certain 3GS iPhones, mostly those sold outside of the USA. It also seems that some of you, who have been able to visit a Genius Bar, have been able to get free replacements. For others, visiting a Genius Bar is inconvenient or cost prohibitive.
While looking for a solution to a MacBook issue, I found this website:
http://www.apple.com/legal/terms/iphonears/outofwarranty.html
Perhaps there is something there that will help you?
It seems that Apple might have a written policy that addresses this situation, depending in which country you are. On the right side of the page there are additional policies that might offer assistance in this situation.
Good Luck.