Your approach was the correct one. You just have to enter the name or IP of a reachable SMTP server on your network - you don't have to install SMTP or any other mail service on your SharePoint servers.
I would suggest checking if your can reach this mail server. Telnet from the SharePoint server to port 25 of the target server works best:
telnet mailserver 25
If you do this from a command prompt and the screen goes black or gives a greeting, that means your command reached the mailserver. To be extra sure, then type:
and if you get a response back you're good to go. The next important step is to check if your SharePoint server can relay through this mail server - better ask your mail admins for this info. But if you really like this telnet stuff, you can check it from there:
If you don't get an error message like "relaying denied" you're probably ok.
BTW, the telnet client is not available by default starting Windows 2008, so you have to add it via add/remove features or via PowerShell:
The whole process looks something like this (my commands are marken in green):