Seems like this happens a lot. One common speed/maintainability scenario is when programmers use an ORM (Object Relationship Mapper) to make dbi code more maintainable, either by building their own (frowned on) or using Class::DBI or DBIx::Class or friends (less frowned on, but still a performance penalty). Did something like this happpen in your case? If so, see OO concepts and relational databases ... Thoughts about Class::DBI and MySQL performance... and super searching will probably turn up more.

What other factors do you reckon could be causing your "more maintainable" classes to suffer? Do you use complicated inheritance? Perhaps then you could recode to use composition instead, which legend has it is often a win. (I've found this to be so from personal experience.)

In any case, perhaps you could just expand a bit on what I quoted. You already talk about this quite a bit in your post, and if you are convinced that this is really the full story, fair enough. But perhaps something else occurs to you.