I'm writing this, as it might "speed up" somebody else finding the cause of the slowness of his/her site.
Sorry about all the time you lost on this. Dues to this very nature (storing url pairs in the database), sh404sef and all other sef extensions that use the same process do add some overhead to a web site, just like Joomla sef add some overhead to sites compared to having no sef at all. Forums are actually the worst extensions to work with because users creates posts all the time. With database-backed sef extensions, it is the creation of a url that takes time. When it is created, it is easy and fast to retrieve from the DB.
All that said, I'd like to point out :
- support for Kunena has only been added to sh404sef a couple of weeks ago, meaning you have been using either a 3rd-party Kunena plugin or even Joomla router.php files. This is really a worst case scenario for speed
- to put things in perspective, my own tests on Kunena shows that sh404sef add about 20% to 25% overhead over Joomla SEF. That is usually something that can be handled by hosting, but may require indeed additional resources in case such as yours, with failry heavy load.