My type before - Relay has always been on, and allowed for all local machines. Again, this has worked for over 2 years until now. I've tried changing 10 parameters and back, with no luck.
Since the email log has NO indication that it's even getting a network connection from UBB, I tried changing the UBB setting for the mail server to the IP address - and things work. So, it looks like the DNS lookup that UBB is doing fails - since the mail software never gets a connection. I tried DNS lookups on that machine, and they work fine.