DrByte,

Actually I posted an update yesterday, but I guess I mustve been careless enough that it didnt come through.

I checked Admin->Configuration->Email Options

Changed from "sendmail" to "sendmail-f" and voila! Problem solved!
Thanks for your advice, I'll keep it in mind when I get 'sudden' changes to my website's behaviour.

I really, really appreciate the support guys.

Go Zen!