Old paper gasket absolutely needs to be removed. Leaving it on can cause a new paper gasket to leak.
Razor blades are a good idea, though be careful as you can actually shave off pieces of aluminum with them. Scrubbing at them with a rag or a sponge dampened with mineral spirits or acetone will usually get rid of the stuck-on bits if you want to keep the factory machined surface perfect. Make sure to wear gloves.