Everytime you remove your cpu, you need to clean off the old thermal compound really well, and then apply new thermal tape/paste/compound.
The thermal compound is there for a reason...otherwise it wouldn't be a requirement. It helps to disipate the heat from cpu to heatsink. By using the old stuff, the contact was no longer 100%, and you introduced air bubbles.
Your P4 has thermal protection, and it will clock itself down when it overheats...which it's probably doing now.
As for your celeron, I don't know if they have thermal protection.
You should really read instructions and guides before playing with expensive equipment. By doing what you're doing, you're actually asking for your cpu to get burned (are you trying to get your parents to buy you a new cpu?)