Well I'm an idiot - the fulltext index on page_text was missing from a default installation. It didn't break searches but probably slowed them down tremendously. Also set engine to MyISAM on page_text to avoid cryptic error messages from MySQL.
dd659f6ba891
Converting all tables on new installations to UTF-8; this may break MySQL 4.0 compatibility; several minor cosmetic fixes; set Powered button under Links to "on" by default