When will they introduce IPv6? They could then allocate a /64 to each customer and the customer can then firewall off their own little corner. 2013 is not a year when IPv6 is optional.
http://digitalocean.uservoice.com/forums/136585-digital-ocea...
"Once the initial rollout of [private networking to] the first region is finished we'll be moving to get IPv6 enabled in our NY2 region first and are targeting an October ETA for the first public beta!"
With that said, you can still technically do just that or just break it up logically. You can have some interesting fun with routing between a few internal hosts. I've had some fun with Quagga on Linode slices in this regard.
Linode currently allocates 1 address per instance I think? It's better than nothing, but really they should do a /64.
I think that would call for a /48† if you're going to split it farther. Handing out /64 per server regardless of how many servers a client has seems just easier to me.
One thing they could do due to virtually unlimited number of addresses is to let you keep them (instead of reusing for other customers) even if the servers are offline. You could create servers with IPs known in advance that way.
Which actually makes it even more convenient to reserve /48† per customer and then carve out /64 per server. So maybe that's a better route.
† or /56 but I don't know if the savings are worth the potential hassle.