[BlueOnyx:11564] Sendmail Authentication errors

[WnA C-S]

Suddenly, with no real changes by me, I've got a few users who try to 
send mail either via outlook or their iphone and they get 'Relaying 
denied. Proper authentication required.'

I had them check their mail and then do a send, but it still occurs.

In the end (because I had limited debug time) I had to put their IP in 
access as a RELAY.

What else could be causing this to suddenly happen?