While there's a wide variety of private non-routable networks across 192.168/16 or even 10/8, sometimes in being thoughtful of potential conflict, it still occurs. For example, I set up an installation OpenVPN once with the internal VPN network on 192.168.27. This was all fine and dandy until a hotel used that subnet for floor 27 on their wifi.
I re-IP'd the VPN network to a 172.16 network, since that seems to be all but unused by hotels and internet café's. But is that an appropriate solution to the problem?
While I mention OpenVPN, I'd love to hear thoughts about this problem on other VPN deployments, including plain ol' IPSEC.
I think that what ever you use, you're going to risk a conflict. I would say that very few networks use ranges under 172.16, but I have no evidence to back that up; just the gut feeling that no one can remember it. You could use public IP addresses, but that's a bit of a waste and you may not have enough to spare.
An alternative could be to use IPv6 for your VPN. This would require setting up IPv6 to every host you'd want access to, but you'd definitely be using a unique range, especially if you get yourself a /48 allocated to your organisation.
We have several IPSec VPNs with our partners and customers and occasionally run into IP conflicts with their network. The solution in our case is to do either source-NAT or destination-NAT over the VPN. We are using Juniper Netscreen and SSG products, but I assume this can be handled by most higher-end IPSec VPN devices.
Unfortunately, the only way to guarantee your address won't overlap with something else is to purchase a block of routable public IP address space.
Having said that you could try finding parts of the RFC 1918 address space that are less popular. For example, 192.168.x address space is commonly used in residential and small business networks, possibly because it's the default on so many low end network devices. I'd guess though that at least 90% of the time people using 192.168.x address space are using it in class C sized blocks and usually are starting their subnet addressing at 192.168.0.x. You are probably a lot less likely to find people using 192.168.255.x, so that might be a good choice.
The 10.x.x.x space is also commonly used, most big enterprise internal networks I've seen are 10.x space. But I've seldom seen people using the 172.16-31.x space. I'd be willing to bet you'd very rarely find someone already using 172.31.255.x for example.
And finally, if you are going to use non-RFC1918 space, at least try to find space that doesn't belong to someone else and isn't likely to be allocated for public usage anytime in the future. There's an interesting article here at etherealmind.com where the author is talking about using the RFC 3330 192.18.x address space that's reserved for benchmark tests. That would probably be workable for your VPN example, unless of course one of your VPN users works for a company the makes or benchmarks network equipment. :-)
The third octet of our Public class C was .67, so we used that inside, ie 192.168.67.x
When we set up our DMZ, we used 192.168.68.x
When we needed another block of addresses we used .69.
If we had needed more (and we came close a couple times) we were going to renumber and use 10. so that we could give every division in the company lots of networks.
use less common subnets like 192.168.254.0/24 instead of 192.168.1.0/24. Home users typically use the 192.168.x.x blocks and businesses use 10.x.x.x so you can use the 172.16.0.0/12 with very few problems.
use smaller ip blocks; for instance if you have 10 VPN users, use a pool of 14 ip addresses; a /28. If there are two routes to the same subnet, a router will use the most specific route first. Most specific = smallest subnet.
Use point to point links, using a /30 or /31 block so there are only two nodes on that VPN connection and there is no routing involved. This requires a separate block for each VPN connection. I use Astaro's version of openVPN and this is how I connect back to my home network from other locations.
As far as other VPN deployments, IPsec works well on a site to site basis but is a pain to configure on say, a traveling windows laptop. PPTP is the easiest to configure but rarely works behind a NAT connection and is considered the least secure.
Using something like 10.254.231.x/24 or similar could also make you slip under the hotel radar, as they seldom have 10.x networks large enough to eat your subnet.