Your problem isn't the storage, it's whatever you are doing locally that is the issue. I've got tens of thousands of files backed up with no issues, across several devices.
You didn't mention your OS. I'll assume you are running Linux because if you are running WIndows/MacOS you are missing a fundamental weakness already.
On Linux, use EncFS which also has a nice GUI manager via GEncfsM for those that prefer it.
Using EncFS means you don't have to upload entire files when you edit them, only the changes are synced. This is efficient, open-source, and works perfectly.
Once EncFS is working, pick any cloud storage you want and sync the encrypted folder(s). I do it with Dropbox + symlinks and it is flawless, no issues for years now.
I've used company_name@my_domain.com for ages. It's too much trouble to go back and update all the accounts to change them all to my real address.
I want to move off of Google Apps. Paid services are no problem. I can't find any email services that both allow anything@my_domain.com PLUS do spam filtering on the catch-all addresses. Are there any out there?
Link to Original Source
Note that the local telco JTGlobal, have placed a comically low bandwidth cap of 50GB/Month. Doing the math, you would use your 50GB monthly ration in less than ten minutes going flat out.
Fortunately two other re-sellers here offer unlimited plans for the savvier shoppers.