Terminal Server Licensing (Per Device) Problem

[Echoboy]

Hi,
Any help here would be appricated.
I have 2 Windows 2003 server running in application mode using (Per device)licensing.
My under standing of it was that using (Per device) looks at the connecting machine for the cal. So if "Xp Pro" Works, "Nt4" Does'nt.
Both server's are setup identical about a week apart,
However 1 server has stopped granting users(All running XpPro)license's saying unable to grant a license as it cannot find a licensing server, however I can still get on fine from mylaptop(XpPro).
We do have a licensing server on the network. But they were not registered with it.
Do the servers need to be registered with it even though they will not be using any license's on it.

Thanks

Stu