I'm troubleshooting a strange issue where auto-attendants hosted by Exchange UM seem to have a 5 second delay between rings stopping and the recording starting. There's just 5 seconds of silence. There doesn't seem to be any white space in front of the recording, and network connectivity between the Lync front end and the Exchange server seems to be working as intended. Anyone seen this behavior before?

I've seen it with .wma files.  Wav files recored in the correct audio seem to have less of a delay.  Try enabling TUI recording so you can call in via phone and rerecord these to see if it helps: http://technet.microsoft.com/en-us/library/bb691404(v=exchg.150).aspx

Also: http://www.petri.com/creating-custom-prompts-in-unified-messaging.htm

I'm using .wav files setup with the correct bitrate/codec/etc. outlined in the technet article.

Strange.  Have you tried recording via the telephone?

Not yet, I'm looking at the documentation you sent to get all that set up.

Weirdly enough, re-recording one of the AA messages through the TUI resulted in a LONGER delay. This is a really strange issue.

I have the same issue. Did you find a solution to this?