Ok, I've managed to solve my own post, I'll give the details here anyway as it may benefit anyone else with a similar problem.
The virus had removed the following registry Key (amongst others):
This starts the whole ball rolling for enabling the Action Center notifications.
When Explorer.exe starts, it looks for this key, and that it what then tells it to load ActionCenter.dll, and monitor for whatever messages it chooses to give.
Hope this is of use for someone else.
How did I find this out?
If anyone's interesting in more detail about how I managed to work this out, I decided to observe what the virus does in a controlled environment. So I created a virtual machine running Windows 7, and deliberately infected it with the same virus while running a tool called "Process Monitor" that tells me every file it creates or deletes, and crucially, every registry key it modifies or deletes.
This is how I discovered that it deleted that key, and I joined the dots up from there.
Many thanks for all those who tried to help, I hope my reply is useful!
I believe I'm supposed to mark this thread as solved?
I'll try to work out how to do that shortly.