Permalinks SLowing down website drastically

We have a fairly large site which was getting extremely slow, we rebuilt the theme, played with a million things and it came down to: no permalinks = fast fast site, permalinks = slooooooow site.

This is bizarre and we are looking at the server’s mod_rewrite but now even sure where to start.