You need to add some users, via the ePO console menu option 'User Management - Users'.
These will then appear as available recipients.
How did you set your smtp server parameters? Do you need authentication or does the sender mail address need to exist? Can ePO server make connections to your mail server through port 25? (just try to telnet your mail server to port 25.)
Is your mail server a cluster or just a single server?
I would go to the SMTP configuration as mentioned by Laszlo. You have to configure your mail server to accept relay for the ePO server.
User contacts is just a collection of email addresses, you don't need to add them if you don't want to and is not related to erros on sending test mails.
You will have to log on to the exchange server with admin rights for the exchange function and add the ePO server in question to the exchange config. You'll have to give it rights to operate as a server that can send mail through this exchange server. Next, check the firewall ports (if there are any FWs between the ePO and the exchange) to ensure port 25 is not blocked. As someone said above, a quick check for this is to simpy telnet the exchange from ePO on port 25. But, remember, if this fails, it may be because ICMP is disabled on ePO or exchange... and it may be blocked by the hips fw rules on epo itself. Get through all this and you should be good to go.