Quite the little dilemma your in. Let's take each step as you have it written;
1. Do I need to backup all of our policies or are they stored in the DB? Likewise for SuperAgent config, client tasks etc.
A1: Yes you need to backup all of your policies.
2. If I have to manually backup all policies, do I just need to select the product in the policy catalog and hit the export button (towards the top of the page) ? Or do I need to export each individual policy?
A2: The best way is to back up, as you should anyway, each and every policy from the policy catalog. You simply export all from each category like McAfee Agent etc. Don't forget your tasks.
3. I presume I will have to check in all software and extensions again?
3A: Check in ALL software and ALL of the same versions as you currently have checked in now. You using encryption or DLPE where we need to think about keys and other factors?
4. Is the registered servers config retained?
4A: The registered servers will need to be setup again. You would want to make sure that all authentication is in place and working anyways.
5. What happens to the recovery keys for encryption? Are they recreated when the agent next checks in to ePO?
5A: What version of encrytion are you using? If you are using 7.1 or better 7.1.1 then when you push a new agent to the system, validate that you got it's key.
6. Anything else I need to consider when having to reinstall a fresh instance of ePO?
6A: Run each ePO server in parallel. And apply your policies and tasks on the new system tree as needed. Make sure all of your repositories are newly created as well, you cannot use the same locations.
Lets start there.
Thank you for the information. I was resigned to the fact that this isn't going to be a straight forward task!