Hi
Dave. I have had a fair bit of experience producing On hold messages a while back. Despite the phone not being a great reproduction medium the idea of delivering a low Fi signal into the phone system is a silly one. Firstly do they want to store a million phone message hence the need for such small files. I would say not.
It is still better to feed in something that sounds great into the phone system. The resultant sound will still sound better on the phone. I actually supplied wave files at 44.1 16 bit but decent mp3's would also suffice.
What is important though is setting the EQ of the final mix before it goes into the phone. What I found worked very well was to get a phone from somewhere and rip off the handset. I connected a headphone jack to the ear piece and monitored the mix through the phone while I applied the final EQ. You do need to EQ a bit. eg roll off the bass and adjust the mids etc for a nice clear sound in the handset and it can be done.