the problem does sound mysterious 🙂 like an episode from the x-files!
question, if you send an email to that firstname.lastname@example.org, do you get the same bounce back? isolating the situation is usually the first thing to do (is it a @telus.com sender that can't locate this domain name? or the other way around?)
if you get a bounceback from your personal gmail for example, the problem likely resides on the email hosting company of your friend.
let us know of the outcome of the above test!