Something is definitely wrong there. You should not have to go through all that for simple agent upgrade from 502 to 504. Are you using Active Directory? or do you have a generic administrative account on your systems? If so, you can force install McAfee agent which will overwrite the current version. So instead of running as a "deployment" task, what you have to do is look at system tree and use the "New Systems" option.
When I do agent upgrade, I even still have some that are on 4.8, and I upgrade them directly to 5.0.4. Most of the time, I can do this with a client task and a tag; when the latest agent is installed, it'll tag that system with "Agent-Latest", and then I have the client task run every hour against all systems that don't have that tag (I have systems that rarely come online, and only for a short time, otherwise I'd do once a day rather than once an hour). No other install or uninstall needed.
For the stubborn ones, though, I have to try pushing an agent deployment, and the really stubborn ones get the "Force installation over existing version" checkbox.
If that doesn't work, then I have to raise a ticket with our helpdesk to manually intervene. But 95%+ I can get with the above steps.
If it's not working for you, you might find it useful to check the client installation log on a failed install. That log can be found in the System %temp% folder under McAfeeLogs, and should be called "FrmInst_<PCname>.log" and "FrmInst_<PCname>_error.log".