I have actually done this, albeit with "only" a few hundred remote connections similarly behind DSL routers. I can't comment too much about the rekeying issues, but a few practical things I learned along the way:
1) When deploying clients, make sure you specify multiple VPN servers in the client conf, vpn1.example.com, vpn2.example.com, vpn3..... Even if you only provide one or two of these now, you give yourself headroom. Configured properly, the clients will keep retrying them at random till they find one that works.
2) We use a custom AWS VPN server image, and can spin up additional capacity on demand, and Amazon DNS (R53) handles the DNS side of things. It is completely detached from the rest of our infrastructure.
3) At the server(s) end, make careful use of the netmask to restrict the number of potential clients. That should force clients onto an alternative server, mitigating the CPU issues. I think we limit our servers to 300 or so clients. This choice was somewhat arbitrary on our part - "gut feel" if you like.
4) Also at the server end, you should make careful use of firewalls. In simple terms, we have ours configured such that the clients can VPN connect in, but the servers strictly disallow all ssh connections inbound except from a known IP address. We can SSH to the clients if we occasionally need to, they can't SSH to us.
5) Don't rely on OpenVPN doing the reconnect for you at the client end. 9 times out of 10 it will, but sometimes it gets stuck. Have a separate process to reset/restart openVPN at the client end regularly.
6) You need a way of generating unique keys for the clients so you can disavow them sometimes. We generate these internally with our server build (PXEboot) process. Never happened to us, but we know we can do it.
7) You will need some management tools, scripts to monitor your VPN server connections effectively.
There is not much material out there about how to do this unfortunately, but it is possible, with careful configuration.