Not sure I see the issue here. IPv6 is how things are moving, although it will take some time for adoption in the US. With IPv6 each device (a vps in this instance) is allocated a single address. Each IPv6 address is a public address, as the specification with IPv6 is there are no private addresses. Enough addresses for every device in the world, multiple times over.
Also, while they may be in the same block, the location is not known as there is no geo-location on IPv6. Many hosts offering IPv6 use a single tunnel for the traffic which is why you see this.
I'm not an expert here, but I think that the "routable" part of IPv6 is only up to /64 (i. e., half the full address). Of course, it is still up to hosters to actually dispense addresses and implement routing in their own network - but it definitely is not true anymore that a single VPS always gets only a single IP, and that extra IPs cost money. I just looked at the documentation for OVH as example, and it seems to indicate that each customer automatically gets a full /64 in IPv6 space (see http://help.ovh.com/Ipv4Ipv6).
Note that I'm not necessarily saying that something needs (or can) be done here, just wanted to point that out.