Here's the final and cleanest method. Skeel showed me the solution the next day at work by pointing me to a new MEL-only command that has been made available since Maya 2009. Somehow this method did not turn up in any of my searches on the subject. I must therefore conclude that it has been overlooked.
All you need to do to reset the initial state now, is enter the MEL command:
This immediately removes the particle cached initial state, and resets your particleIDs. This method completely removes the initial state.
Here's the video to show it: