How do you clear the templatecachequeries table?
You can clear the cache from within the settings section of the control panel. It's possible to select which specific caches to clear if necessary.

You can try manually clearing the cache tables. Test it on a backup first but I have done this in the past with no ill effects.

It sounds like you need to be adding the "globally" keyword to your cache tags. This will drastically reduce the number of rows in the cache table and most likely speed things up too.