I recently started a new job and have slowly been becoming the 'go-to' IT guy as nobody else in the office has any real computer problem solving experience. 

This has led to some strange discoveries and weird hacks people have done over the last 12 years in the current office but one in particular is troubling me at every turn. 

It's regarding outgoing SMTP servers but first i'll explain the problem. 
- My boss travels frequently for work so needs email access abroad. 
- Our email is hosted by some place called flashlevel.net and the outgoing smtp server settings they ask me to use are mail.archwksp.co.nz and port 26 with no ssl
- My boss' laptop had its outgoing smtp server set to smtp.xtra.co.nz on port 25 which would work fine here in NZ but would fail in AU etc.

When he would travel outside of NZ he would have to enter a local smtp server to get his email to send. This obviously caused issues as he'd have to fiddle with his email settings all the time and I'd have to repair the 'fixes' he'd made.

I changed his settings to the default flashlevel settings above and he was happy until recently when several emails have been bouncing back. 

I've tracked it down to when we send email using smtp.xtra it goes through fine, but if we send from mail.archwksp it fails. 

I was bemused to say the least as to why we were using an xtra smtp server when our email isn't hosted with xtra, but I was more confused when emails to only a couple of addresses failed from the mail.archwksp settings. 

99% of all email works fine, it's just to these addresses that it fails. 

The errors aren't consistent however most are "retry time not reached for any host after a long failure period" 

Questions:
Why is this going on? 
Where should I start looking to find a solution?
Also, is it a simple job bringing the email hosting back to someone more local/not unknown?