From what you describe, it looks as if some program - a registry cleaner perhaps, an antivirus program or even Windows update - corrupted or deleted Host registry entry (key). The Host keeps all its settings, including Internet-ID connection settings in Windows registry, in this key:
Even when it works I have to wait a few seconds for the mouse cursor to change.
This is how it is supposed to work. You should allow the program 1-3 seconds before it receives a response from the Host and finish the operation. Performance usually depends on the kind of connection used - on a LAN it should be faster that when using the Internet-ID.
We analyzed the logs. It looks like the network connection with the server is very unstable for some reason. Just as an experiment and to exclude the port conflict reason, try to use another port, something less used or even default (5655). Don't forget to change it on either side of the connection (Viewer, Server and Host).
We can still connect to them using RDP with VPN without Remote utilities when remote utilities doesn't work.
Sorry, it doesn't make sense to compare direct connection (RDP through VPN) with indirect/mediated connection (RU via a relay server). With Remote Utilities you can connect directly as well - see this tutorial.
That said, although I didn't see the Host logs - only them can give some definitive information about the issue - I can guess that you might have a port conflict. You use port 443 as communication port for the server. This is a widely used port and perhaps, some other service or application also uses it.
The only reason behind using port 443 is that this port is often open by default in many organizations. But that doesn't necessarily make this port "more secure" than other ports. Ports are just numbers, you can use any port because security has nothing to do with the port number. Rather, it's implemented in the application itself and transport protocols.