As an interim measure, can we change the
user group rights such that only administrators can create pages? Most of the pages we want already exist, and although it might suck to have to request an admin create a page you want it's better than this deluge of spam.
Couple that with a mass deletion of the orphaned pages and user talk pages (if possible) and we should hopefully be able to keep things under control. Moving to a third party wiki hosting service is an option, but the migration would indeed suck.