The easiest way would be to reimage the server or revert to its base OS snapshot, so that you have a guaranteed clean environment.
If thats not an option, then once all agenst and plugins have been removed from the clients, you can use SIM to remove the SMP and its solutions. You can also do this via "Programs and Features" too.
I would then delete all Altiris rgeistry items (this is a good point for the clients too), and then reboot the server.
I personally would keep the old database and then install 7.6 new either with its default database name (rename the old one first) or with a different name. This will allow you to have a clean db in order to use the old one as historical data or as a reference on how you did things in the past, as well as have the opportunity to upgrade the old one to the 7.6 schema.
Now, if all you are worried about is HF3, why dont you roll that back, and then upgrade to 7.6, unless you really wish to start with a clean 7.6 application and database?
SK