I'd just like to add that I've found this to be the case, too, in my current version of SublimeText 2 (latest build, OS X 10.7.2). Like the previous poster, I sometimes have to do a search & replace on a large SQL dump for migration purposes. My current dump is only 7 MB, but as we speak SublimeText is still processing away after clicking "Replace all", turning my MacBook Pro's fan on high as a result. It feels as if it's been 10 or 15 minutes and I'm about to kill the process.
MacVIM, on the other hand, executes the same search & replace on the 7 MB file in under a second.
I have no plugins installed on SublimeText 2. Maybe I'll try a fresh install just to be sure.
By the way, I have successfully done search & replaces on large files such as this using SublimeText 2 maybe a month or two ago (the last time I had to do this kind of task) - but that's quite a few builds ago now.