Windows Deployment Services: Duplicate computer name stops imaging

We are using Windows Deployment Services in mixed mode to image XP computers.
We are having a problem imaging five out of eight Dell machines. The OS
Chooser stops at a screen indicating the computer name contains invalid
characters. On the deployment server we get an event saying:

An error was generated by OS Chooser. The error code is in the record data.
User: user_name Domain: domain.name Computer Name: $DUPLICATE-1d93b.

Searching our Active Directory we can't find that computer object. Changing
the Client Naming Policy to different variables doesn't help.

Has somebody dealt with this problem before? What solutions did you find?

Any help will be greatly appreciated.