Sometimes old solutions work best

I have a 4.8 MB file where I needed to do a replace that would happen about 850,000 times. I tried it in a few different editors:

• Notepad: It looked like it was taking 3 seconds per replace so I killed that. I don't have the time to wait a month!
  
• Source Insight (My preferred code editor): It partially suceeded in a few minutes but it ended up corrupting the output since it "ran out of undo space". Time to ask my co-workers...
  
• jEdit: After running for at least 15 minutes I killed it.
  
• TextPad: After running for at least 10 minutes I killed it.
  
• sed: 10 seconds!
  

BTW my machine is a hyperthreaded P4 3.06 GHz with 1 GB of RAM with a serial HD.