I'm beginning to feel like your stalker
We've always seen it with Outlook and Macmail where I work (which meant it predated 2009 when I started here). I've only skimmed that old thread, but it looks like poplocks causes it... Kind of makes sense if that takes priority over smtpauth with Outlook sending an auth request and Qmail thinking it doesn't need one.
With regard to spamdyke and poplocks, I'm pretty certain that its not compatible and thats the reason why we don't use spamdyke (worryingly we've started to these last few days!). This also makes sense since it hits spamdyke before it hits plesk/qmail/poplocky stuff and spamdyke will just tell the user to piss off since it knows nothing about the poplock auth.