I like my dedis and larger VPS's to be paid at least a full month in advance. With smaller vps's it's less of an issue to just pay the invoice that arrives a few days before the service will otherwise expire. The concern is what happens if there's a snag with renewal, e.g. because of (common) problems with Paypal. If that happens with a small VPS it's not a big deal to backup the files to another host or download them to a home PC. With a big server (100+ GB to multi-TB's of data) it's much more of a hassle to migrate in an emergency. You have to find a new host with plans of enough capacity, you need a way to sign up and pay for the new plan (maybe not easy if your paypal or CC is frozen), there's potentially a wait to get the new plan activated, and then there's the logistic hassle of transferring that much data over the snail-like internet. I went through this adventure (last minute migration of about 500GB) from a storage VPS to an OVH dedi, then later had some drama with OVH because of Paypal hassles, so now I have my main OVH server on a 3 or 6 month cycle and attempt renewal at least a month ahead of time. I figure if the renewal goes wrong, the 1 month runway will let me work out an alternative.
For selection purposes I give extra preference to hosts that can accept payment with the fewest possible intermediaries, e.g. it's a big plus if they can directly bill credit cards instead of requiring Paypal/Amazon/whatever. It's an even bigger plus if they can accept regular checks/money orders/wire transfers/cash/bitcoin, since there are even fewer ways for those to go wrong.
I'm fine with low end annual VPS plans ($15/year or whatever) since the amount of $$ at risk is not enough to get worked up about. I had one that sucked pretty bad so I didn't renew, no big deal. It was the first one I had tried and I figured the educational experience was worth the $15 all by itself. Once I got to understand the market a bit better, I haven't had any serious problems, though that partly results from generally not pursuing the lowest priced offers.