The number of letters allowed in the search exponentially increases/decreases the search database size. With over 1.7 million posts, the database had gotten rather large (is that an understatement).
The search database is built based on this value, and a couple others.
At some point the server load is just horrific for searches due to the sheer size of the database.