I'm at 1.7 million posts (but on 7.2.2), and searches come up very quickly. My current server is new, but nothing spectacular... single quad core at 2.4 GHz, and 4MB RAM.
A few years ago when I was closer to probably 1.2 million posts, the site was on an old server with only 512 MB of RAM. A search would bring it right to its knees. I can't tell you if mysql was setup properly, but it was a very bad situation.
