Recently i was surfing the web, searching for things on phreaking and the like. One of the things i found was kind of interesting, although i did not think much of it at the time.
The trick requires a redbox, a paperclip, and one of the newer phones with redbox protection (the muted ones). First, before trying to generate the tones, you stick a straightened out paperclip into one of the holes in the mouthpiece, then touch the other end of the paperclip to anything metal. From what the artical said, this will cause something in the mouthpiece to short out, taking the mute off. It also said that on some phones, it will require a firm push on the paperclip into the mouthpiece.
I have not tried this trick, and i doubt i will anytime soon, mostly because i have limited access to pay-phones. Please reply or e-mail me with how it worked. i will try finding the article later and posting it in a reply.