I recently did an AWS certification. I hadn't done much Cloud before and I was really impressed by the platform. It's really amazing and as they have over 90% of the market and massive ongoing investment, it's a great choice. I'm not aware of any backup restriction with any of their database services. What Database are you using? If none of the AWS DB services suit, you can always run your own DB instances on EC2 and backup to S3.
Tired of over zealous filters claiming your good email is spam? Then try Email Saviour, it's toasted hosted. (Thanks Don Draper)