Camoron,
The DNS Searchlist is not what is causing your issues at this point. If it were me I would use the customers domain name for the DNS Search List though.
So if their email address is sally@test.com then in the DNS Search List I would put test.com so that it would match for anything the system would send as an anonymous user.
Now for the Error you are getting the problem could be that you don't have access to the Internet or the DNS you are using is not resolving properly in order to find smtp.office365.com.
By the way what port are you using for sending your emails to this? 25, 587, or 465?
Thanks,
TE