Do the users with the problem have home routers? It could be that the routers are clearing their port translation tables after a period of inactivity.

A SSH session is never really idle as packets will be exchanged to update keys and such.

The telnet socket has the keepalive option set, but the default time for keepalive packets to be set is after 2 hours of inactivity. You can control this by changing the value of the MultiNet kernel variable TCP_KEEPIDLE. The units are 500ms, and the default value is 14400, which comes to 2 hours. 10 minutes would need a value of 1200, so pick something lower just to be safe: