In addition to MrHoffman's excellent commentary, when sending email (as he mentioned) this will be a communication between your Mac and your email provider's SMTP server. However, the first thing that your Apple Mail client will do is perform a DNS lookup for that server.
With that said, there also may be an issue with either the DNS server(s) that you are using or with the DNS server settings on your Mac. One quick test would be to try sending emails from outside your network ... unfortunately, since you have a desktop Mac, that wouldn't be practical.
By default, your Mac is probably using your ISP's DNS servers or pointing to your local network router (which is basically the same thing.) What you can try is use another set of DNS servers, like those from Google or from OpenDNS, to see if that can help.