please do this:
1. pick one problem client (and check if you really do not see in ePO tree)
2. enforce an ASCI from the client (either from the agent interface if you can or issuing a cmdagent.exe /p command from withitn agent install folder)
3. check - regularly - server.log on the ePO server for the name of this client and see what ePO says.
You might see something like ePO rejecting the client or otherwise abnormal handling of it. could you post here the relevant excerpt of server.log?
I would say you are having some duplicate AgentGUIDs and/or MAC addresses on top of this, which might contribute to this issue, but as far as I know the McAfee Agent 4.5 has support to regenerate its GUID when ePO 4.5 server tells it to do so... you might not have ePo 4.5 I suppose....