If Gmail proved anything, it was that people would, for the most part, accept any terms of service. Or at least not care enough to read the fine-print closely.
True. It's basically impossible to fully self host nowadays. You can host for your local users and use a/your provider to route and possibly act as your MX if you really want to go that way. In that case most hosting providers that let you edit the DNS files will do.
I have. My main problem wasn’t so much that I was getting flagged as spam, but that the spam filtering on the receiving side was just awful. I also don’t send many emails so it may well be the case that I just happened to not experience that problem.