Do you really need a server? You can launch a more powerful EC2 instance (EBS backed), upload your data, and stop the instance (alternatively you can create a snapshot and terminate the instance). Next time when you need the backup or back up more data, just start the instance. You pay the full price of storage and data transfer, but not the CPU. If your other servers are within AWS, you even don't need to pay for the data transfer.

5TB of storage on AWS would cost >$500/month.

You could buy a server and colocate it for less than that.

You're right. That's a lot if OP really needs 5TB of storage. It's still an option if OP begins with less storage.

I have not found any virtual with storage cheaper than Amanzon/Google (0.10 $/month/GB).

you can find "backup" VMs for cheap but:

  - these are typically OpenVZ (can't pick your kernel options)

  - very busy and slow (they meant to be for backup only.

http://ovh.com has physicals at around 40$/month with 2 x 1 GB disks.

Have a look at the servers that hetzner.de is offering, maybe there's something there for you, also have a look at their auction.

I don't know if it fits your needs but dreamhost has some hosting where you pay once and host "forever"

Some Kimsufi servers have quite a bit of disk for their price. You'd need to run a RAIS, though.