Network Utility Traceroute- What does this message mean?

Usually it means the host is offline.

This particular error indicates a problem with the domain name lookup system (DNS). That's what converts the mail host name to an IP address. It's telling you that it doesn't know what "mail.xxxxxxx.com " is. You can play with that via the Lookup tab in the Network Utility. You can find your DNS settings by pressing the Advanced button in the Network Preferences.

If it's the case that you can get to everything else in the net fine, but just can't look up the name for that host, and you're sure the host name is correct, then the problem isn't on your end. Most likely with the net admins for your mail system or for your ISP. That means that others are probably in the same boat and that the problem will probably resolve itself. But you could call your ISP or email provider.

DNS problems can be weird. How about this: use Network Utility to look up the IP address of your mail.xxxxxxx.com server. Then go into Mail and replace the name of the server with the IP address.

The risk you run with this is that if your mail provider changes the IP address of their server then Mail break. That's one reason that DNS names were invented. But that probably won't happen often, or at all, and if it makes your problem go away you'll not only be better off than before but it will also be diagnostic.