I don't have the SQL settings in place to test it, but you can try this:
Open applications/advancedtagsprefixes/modules/admin/manage/tools.php
Find: (line 275)
$keys = \IPS\DB::i()->select( array( 'tag_aai_lookup', 'tag_meta_app', 'tag_meta_area', 'tag_meta_id', 'tag_id' ), 'core_tags', NULL, '`tag_id` ASC', array( $start, $perCycle ), 'tag_meta_id' );
Change to:
$keys = \IPS\DB::i()->select( array( 'tag_aai_lookup', 'tag_meta_app', 'tag_meta_area', 'tag_meta_id', 'tag_id' ), 'core_tags', NULL, '`tag_id` ASC', array( $start, $perCycle ) );
Save, retry.
It will be slower (running based on tag instead of topic), but I think that will be the only side effect.