Hello Sivanesan,
As this is a new configuration i will start first with some basic questions:
1- Is this scenario phone A to phone B for all users or just a specific user?
2- If it's only one user then check under User>Edit> Mailbox
2.1- That it is mounted (see check box).
2.2- That there is no negative value on the number of messages or size.
2.3- Check if the Mail Store is the intender if you have more than one.
3- You state it says "your Message has been sent" are 100% it is the correct user and not the Opening Greeting? You can confirm this if you have configured a customized greeting for the user, otherwise use rPSM.
4-If while you are leaving the message you hit playback do you hear your message (to rule out one-way audio)
5-Does the message meet at least the minimum time recording, this is stated in System Settings>Advanced>Telephony> Minimum Recording Duration in Milliseconds.
6-Any additional input that you consider pertinent.
-DavidRP.
