You can't be doing it for long enough time and didn't run into AMD's "chewing gum" paste which would stick like crazy glue. It was used as late as at least FX processors. Not small number of CPUs was ruined by pulling coolers off together with CPU. Alcohol is not that difficult to get, Isoprpyl is used by printing services by gallon or barrel, Methyl for some kinds of paint thinner and brush cleaner and concentrated Ethyl in food stores.
It might be splitting hairs but paste is there to fill up small imperfections between surfaces, mechanical removal can't get in there, only solvent can. Not all pastes use same type of silicone and heat transfer filler so essentially new paste is not new any more, it's still in those scratches and imperfections.