Yes, that law is a bit scary, it may push people to start using encryption for everything by default. Of course only end-to-end encryption really protects communications, so the tunnels you want are of limited value, but that is entirely your business.
Lots of bandwidth and no storage is going to be a custom setup, I wouldn't look at stock VPS plans for that, but for providers you can come to an arrangement with.
The hardest part is going to be the IP addresses. Of course if you just buy one VPS per client you get one IP address, no problem. Your usage would be clearly justified and normal. The routing might be a little tricky to set up but you only have to do that once.
You could also use a single VPS with a huge number of IP addresses. This can be trickier, not because your use isn't justified, but your chosen provider should probably handle it as a separate RIPE request for you so everything is clear and in place from the outset.
There are some issues you didn't touch upon, such as what you are allowed to do from your VPS (e.g. IRC communications are often not allowed, so even running an IRC client over the VPN would be forbidden), and processor and memory requirements. OpenVPN is pretty good on memory, but encryption does take quite a few cycles.