Varying levels of anonymity in purchasing, accepts cryptocurrencies, and compatible across most of my devices. I've also had some great customer support w/ them.
The point of destroying is presumably that you don't pay whilst you're sleeping, or otherwise not using the server.
Re: data, you can (optionally) do a wipe when you destroy a DO, but you could just delete the logs or turn off logging, which would be faster. Having said that, I'm not sure what in the logs would be harmful to you.
I've used https://www.privateinternetaccess.com/ while traveling abroad. It has worked quite well.