I am bumping this topic because the problem still persists. And it seems that in both of the above replies the authors failed to properly read the post before replying.
Again the issue happens on all clients. And I verified as of today that it happens in both Linux and WinXP. I've checked to make sure that Identd settings are correct. I've upgraded all software and firmware.
Something tells me that if I can find the origin of the random string as appearing in the pasted log above, I can help track the issue. There should be no reason why a random string like that should be passed to the server.
So the issue is most definitely connection or software related. The problem is resolved temporarily after the PC is simply restarted. But restarting frequently is a major pain in the neck. And this was not a problem until the reformat occurred.
Any suggestions from anyone? (And please... Read the post thoroughly this time.)