Just an observation, but if tied hashes are slow, and sorting hashes based on complex operations are slow, and regexes are kind of slow... this code must really break down with a large number of records.

This seems to be a classic case where taking the time to load the records into a (SQL) database and then query the database would produce cleaner code with (potentially) a speed savings of (who knows) 10x? Use temp tables or temp views if you must.