Some of the more dependable options for affordable servers, in my experience:

  - https://contabo.com/en/vps/ (they used to have a reputation for overprovisioning, but stable service)
  - https://www.hetzner.com/cloud (they asked me for my ID photos for verification, but otherwise one of the better options)
  - https://www.time4vps.com/?affid=5294 (affiliate link, I use them currently for all of my long term hosting)

Another commenter suggested lowendbox, which is a good option for scoping out offers, but sometimes companies just take the money and run off (as happened to me once personally), generally look at whether the company that you want to become a client of has been around for a while and hasn't recently changed hands.