Sounds like a problem with the repositories rather than an issue with the McAfee Agent.
You should try a full replication from your master repository to all distributed repositories.
When the McAfee Agent is removed (actually, only the management agent will be removed, the updater part is part of VSE) it will update from the McAfee FTP and HTTP website. When the agent is installed, it will update from the repository list that is part of the agent policy within ePO.
My first impression is that this is not a VSE issue, but an ePO issue...