iPhoneAlley details a technique to trick the iPhone into using any custom audio file as your voicemail greeting.
At present, you have to record your greeting by recording directly into the iPhone microphone -- the results of which are average, of course.
Besides creating an audio file in the right format (Adaptive Multi-Rate), you also need to trick the iPhone to upload your new greeting to the AT&T servers:
On the iPhone, go into voicemail and tap "Greeting". Record a few seconds of something and tap stop. Before you tap save, use iFuntastic or SFTP to navigate to /var/root/Library/Voicemail on your iPhone. You'll see a file called "Greeting. amr". This is the audio you just recorded. Delete that file and replace it with your custom message which should then be renamed to "Greeting.amr". Tap "Play" on the iPhone to verify your message works. If it plays, tap "Save" and your custom message will be uploaded to AT&T's servers.
Of course, this option is only available for those brave enough to hack their iPhone.
