The fact that GC-ing old collections takes up to 5 seconds is not so strange. That's why this kind of garbage collection is posponed as long as possible. The only reason for the GC to collect the old collection garbage, is when normal garbage collection is no longer sufficent.
In general, this is an indication that your application can't handle the load, or has a small leak in. For your kind of app, an app that handles a continous flow of requests, and doesn't deal with request bursts, this is no normal behaviour.
You should check your app again. Assigning null values to objects, in particular collections, that are no longer needed is good practice. Check your application for global collections that might keep some sort of an hidden handle to your datastructures, or something like that.
If you are absolutely sure you can not improve you code anymore, try thinking about the load. I don't know how you handle your requests. Do you start a new
thread for every request? Do you use a threadpool with a queue, or just one thread with a queue? Or one thread w/o a queue? In any case, your server might be overloaded. If you send more requests than your server can handle, and you don't give the server time to catch up, the queue of incoming requests only grows and grows, until you get an OOM. Maybe you want to cluster your program and divide the requests among the different machines. It might be a bit of programming work, but I think it shouldn't take too long...
Good luck
Kris