The access log that they posted shows an odd URL, however if your support would have actually tried to go to that URL, they'd see that it actually just gives the standard UBB error message as all of the fields are sanitized. So, that's not the issue. It looks like just some sort of odd URL that is being accessed because of a search.
I see you have a VPS. The biggest question is has MySQL been properly tuned, or are you just running the stock MySQL config?
An example of why a properly tuned MySQL is so important. I just worked on a site a couple weeks back that has well over 2 million posts. They were running a stock MySQL config, and were getting load times anywhere from 1 second to 15 seconds. Searches taking 30-60 seconds.
After proper tuning, everything is in the subsecond range with searches taking 1-5 seconds.
You don't have a huge forum and generally when viewing your site right now, everything is very quick. Typical debug line I'm getting is:
Generated in 0.156 seconds in which 0.040 seconds were spent on a total of 22 queries
Looks like you have about 50 users online right now. So, under normal conditions such as these, everything appears to be running fine and fast. When you get slowdowns, it would be useful to see the debug line to see if it's coming from MySQL or from just general server slowdown.
Another thing is if you have SSH access to the server and if it's a Linux box then when you get the slowdowns you can run the 'top' command to get some info on what all is going on at that particular time.
