NAT Traversal is the standard solution for what you are describing. Specifically, you need to verify the NAT Traversal keep alive setting. Let me explain.
More than likely, you are using IPsec in ESP mode. In a non-NAT traversal scenario, your data packets will look like this (after negotiation):
[Outer IP header][ESP Header][Encrypted/Authenticated Data][ESP Trailer]
The outer IP header will include the the Source/Destination IP of your VPN gateway device (your NSA 2400) and whatever WAN IP the remote office is using.
In your case, you have multiple clients sharing a single source IP -- which is a very common PAT configuration. As such, the Remote router needs to re-write the source IP of each of your clients, as well as the source port. If that router were to have encountered a packet like the one above (with no L4 header between the L3 header and the data), it would drop it claiming it is a malformed packet.
NAT Traversal inserts an additional L4 header in the packet. So it would look like this:
[Outer IP header][NAT-T UDP 4500 header][ESP Header][Encrypted/Authenticated Data][ESP Trailer]
This header starts with UDP source and destination port 4500 (by default, this is configurable). The destination port typically does not change (on route TO your VPN head end device). The source port typically does get changed by the transient NAT device (in this case, the remote office router).
Now. MOST Stateful Firewalls or Routers have a very low UDP connection time out. UDP is, by nature, connection-less, so it is very common for UDP connection timeouts to be less than a minute. Cisco ASA's are 30 seconds, if I recall (don't quote me, its from memory). By comparison, TCP timeouts are inherently high, because usually the stateful device is looking for the RST or FINs to purge an entry from its connection table. A TCP timeout is just a stop gap in case both ends of the communication exploded simultaneously and weren't able to send out a RST/FIN. So a higher TCP timeout than UDP timeout is normal, and even suggested behavior.
With that said, we can describe what is probably going on with your issue...
If the first time a remote office client connects, and their NAT-T header's source port gets re-written to 2222, the VPN Head end device is going to expect all future communication for that particular VPN connection to arrive with a source port of 2222. It will also encapsulate and send all return traffic back to the remote router's IP, with a destination port of 2222. This will work just fine, so long as this particular NAT translation stays active in the remote router.
But IF the Remote Router purges its NAT translation table, the next packet sent from Client to Server will get a new UDP source, say 3333. When that gets to the VPN Head end device, it will consider it a new "connection", and expect a full re-negotiation of IPsec (which from a security standpoint, is the right thing to do).
Additionally, if the Remote Router purges its NAT translation table, and the next packet sent is from Server to Client (aka, destined to port 2222), the Remote Router won't have any record of an outbound translation for that source port, so the packet will simply be dropped. Remember, PAT is uni-directional.
All that said. Since its common and perfectly normal for VPN connections to go silent. There is a function built into NAT Traversal called the "NAT Traversal Keepalive". It is simply an empty packet that is sent every 10-15 seconds (differs by implementation) from Client to Server, and the sole purpose of this packet is to keep the NAT translation alive in transient NAT devices, like the remote Router.
So it sounds to me like you have your NAT Traversal Keepalive set to too high. I would start by decreasing that one. Because its a software change you can make on your Head End device, and should affect all your clients, without forcing you to replace hardware on the other end.
Lastly, to re-iterate what Ricky mentioned. If any time out needs to be adjusted, it will be on the Remote router, not on the VPN Head end device.
Best Answer
While there is no formal "connection" with UDP there is still a convention that clients send requests and expect to get responses back with the source IP and port swapped with the Destinatoin IP and port.
Stateful firewalls and NATs therefore assume that packets with a given combination of source IP/source port/Destination IP/Destination port and the corresponding combination with source and destination swapped form part of a "connection". This allows rules like "outgoing connections only" to be applied to UDP and allows reverse translations to be applied to response packets.
Unfortunately the firewall or NAT has no way of knowing when the client has finished talking to the server. So it has to wait for a timeout before removing the entry from it's state tracking tables. That is the timeout you are setting.
In principle it would be possible to build a NAT box that used a stateless approach for port forwards while maintaining a stateful approach for outgoing connections but it's simpler to just use stateful NAT for everything and it sounds like this is what your vendor is doing.
Unfortunately as you have discovered this sucks for stateless UDP servers serving large numbers of small requests. You end up in a situation where the firewall consumes far more resources than the sever itself.