If messages are being recorded by Unity but not getting to Exchange, they might be showing up in the \Commserver\UnityMTA directory (check root and also \Failed directory under here). If messages are stacking up in here, you very likely have an Exchange connectivity issue. The Unity application event log is a good place to get clues about what the problem might be.
If there are not messages in \UnityMTA, then it may be that Unity is not actually recording anything when you think it is. You might have a situation where audio is transmitted from Unity to the phone (so you hear the prompts OK), but audio from the phone to Unity is not transmitted (one-way audio). So even though you are recording a message, Unity is not getting the voice data. One way to check if this might be your problem is to review a message you have just recorded. If you try to review the recording and nothing is there, you should look into a potential one-way audio problem - this doc might help:
http://www.cisco.com/en/US/products/sw/voicesw/ps2237/products_tech_note09186a0080093c11.shtml#topic1
