-- (deprecated) Microsoft Windows OS (XP/NT/Vista)
---- 550 "Unknown User"
kaled - 12:53 pm on Feb 10, 2010 (gmt 0)
The firstname.lastname@example.org header is empty
So that rules out caching issues.
This suggests that the problem is somehow related to the domain name - are there any non-ascii characters in it? What happens if you place the domain name in uppercase? What happens if you place the username in uppercase?