There's a bug in iCal that in some situations will show every name twice when adding attendees to an event. Adding one of them will always give an error (the oh-so-not-helpful tiny exclamation mark next to the name). iCal will still add that “ghost”, but the invitation will obviously never be sent.
At first this looked a bit like the proxy bug, but since this isn't about delegates, but actual user accounts (and since running proxyclean didn't find any errors) I turned my attention to Open Directory. Luckily, iCal Server 2 comes with actually helpful logging, even at Information log level, just:
tail -f /var/log/caldavd/error.log
and you'll be able to see exactly how caldavd is talking to OD. Looking at that I was able to determine that OD was actually returning all the right search results (when the user was typing a name of the attendee). But even when OD returned just 1 record, iCal would still show 2. Then I remembered seeing a button iCal > Preferences > Advanced called “Clear Attendee Cache”
“Yes! The attendee cache! Sounds like just the thing!” - I yelled, only to find the button no longer there, in 10.6:
Well, let's make that “button” ourselves. Fire up Remote Desktop, select the ailing machines, Click “Send UNIX command” (as the currently logged in user), and:
killall -m '^iCal$'
mv ~/Library/Caches/com.apple.iCal ~/.Trash/
open /Applications/iCal.app/
And voilà! Problem “solved”!