If they are consistently not reporting on new actions until the client is restarted, it is likely a firewall is blocking UDP/52311 from the Relay to the Client. See Troubleshooting Client Reponsiveness for a series of troubleshooting steps I’ve put together.
What operating system are the clients? We have content in the BES Support site to detect & correct host-based firewall for Windows and RHEL; I haven’t checked for CentOS or Ubuntu lately.
You might also consider Command Polling or Persistent Connections, also discussed in that post.