The Swedish parliament just passed a law mandating all information passing the Swedish borders to be copied to the government (no kidding). We wish to offer people VPN tunnels out of the country to protect their communication and therefore need:
* A location with good connectivity with Sweden (like somewhere in Europe)
* A location where traffic is not normally routed through Sweden (such as Finland)
* Lots of bandwidth
* Many IP addresses
* No storage space
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.
Blue Room Hosting - High availability UK VPS KVM Plans - Multiple OS support. Virtual console and CD drive.
This is because for the scale you want, the hardware is usually rack mountable 1U to 3U in form factor, but is not general purpose servers. They may start out as x86 boxes, but have hardware assisted crypto acceleration layered on top. There are two of them cracked open on the shelf above my head awaiting completion of firmware modifications.
The vendor thinks they are tamper proof, uhm, nope ...
Another vote for NL here. 040hosting is NL based and hangs around here.