Your best solution is a VPN as you've already surmised.
This requires a little more management than what you're currently doing: You will need to set up either a VPN client on the managed machines, or more realistically a VPN tunnel between the remote network and some central management hub that you administer.
If your clients have static IP addresses you can also VPN in to their networks from your management site.
Any decent VPN solution (OpenVPN, Cisco VPN concentrators, VPN tunnels from a PFSense firewall) can meet all of your requirements (They are "easy" to configure if you know what you're doing ; Any solution worth using supports some kind of security ; All can be configured to recover from connection drops).
In your particular case I would recommend eliminating "those cheap routers" and deploying a proper managed router with VPN support (PFSense, a NetScreen, any Cisco router with VPN capability).
You will be doing more work initially (configuring the routers, learning how to manage them), but the payoff after 3-6 months will be substantial: you'll be offering a new service that you can charge for (money is good), and you'll have better management capabilities for the existing work you do.
(If you clients already manage their own firewalls and have decent equipment you can also work with them to establish the tunnels or grant you VPN access, but it sounds like your clients are not at that level of capability...)