The template loading and saving being slow could be that the physical pages belonging to the templates table are spread across a large database. Accessing a template then requires reading from lots of different sections of the database file (a template is stored in multiple records, unlike a recording which is stored in a single record). This might happen if they change their templates often.
Recordings are usually all in one place in the database, and purging frees up large sections at a time, so searching may never have the same problem.
Try a reclaim database space (only once!), and see if it speeds up. That will put all the pages belonging to the template table in a single place.