There are two main parts to the Hamachi application:
The first exe runs as a service of the operating system. It is that exe that creates/establishes/maintains all of the VPN connections (be they relayed or direct).
The second exe is the User Interface (or Graphical User Interface - GUI). That is the part of the Hamachi app that you see and interact with. It sounds like you stopped this exe from automatically starting.
These two programs "talk" to each other. When you tell the GUI to turn off, it tells the service to break all of the VPN connections. The service also writes the on or off state to a file named h2-engine.ini. When you restart your computer, the service reads that file to see if it should make the VPN connections or not.
I would guess (and it is a wild guess) that some anti-virus/anti-malware/firewall software is causing your relayed connection. You do not see this after a reboot because the Hamachi service starts and makes the VPN connection before the "security" software is fully loaded and functional.