After applying @ChuckPa’s script from here I’ve noticed real improvements! It seems rebuilding the database is needed every once in a while and it actually makes a difference. I think that Plex should automatically do this during it’s maintenance!
