check the agent logs on the machines to see what is happening when they are supposed to be updateing the patch:
C:\Documents and Settings\All Users\Application Data\McAfee\Common Framework\Db
I will move this thread to the EPO boards where you will get EPO support, if you look at the stickly threads on the epo boards you will see a pointer to how to obtain all the troubleshooting logfiles from your server installation aswell