Hey Gang....
Great info in your posts. I was having the same problem, and just clued into the simplicity of the fix.
When in 'Host Settings' > 'Advanced Settings' > 'SMTP Server Settings' section, my problem was I would enter the SMTP Server and port: info, select Basic Authentication, enter the full email address and password, then I would hit the TEST button. The password would disappear, and I would receive an email confirming the test was a success. Then I would hit the Update link at bottom. At this point, I would log out, and attempt to register a new user. All would go well, but I never received the email with the verification code.
The fix for me was simple. Just didn't see it. I entered the proper info as stated above, and rather than hit the TEST link, I went right for the Update link at bottom. Hitting the TEST link reset the info I entered making the changes unsuccessful.
So, enter your info, and just hit Update. Should be fine.
I have a Virtual Dedicated Server at Godaddy, Win2003, SQLExpress2005, IIS6, ASP.NET 2.0 and running DNN 4.5.5. All's well.
G'luck