Could it be that the VPN Tunnel drops momentarily? As opposed to deskphones, the Presence connection 3CXPhone apps have to the 3CX Server is constant so, even if it drops for a moment, the deskphones usually will not go unregistered but you would get this message.
To see what is going on, on one of the PCs running the 3CXPhone app, once this occurs I would go to %appdata%\3CXPhone for Windows\Logs\ and open the 3CXPhone log file to see the error, that might point in a certain direction.