I mean, why not use @startupmail.com for your personal addresses and have your app use @startup.com? You can set up aliases like firstname.lastname@example.org so the obvious guess-address still works, but this way your users don't end up asking "is this legit?", your corp emails still won't get blocked for spam, etc.
I really dislike the UI of sending app related emails from a different domain. It's an ugly solution to what may be a non-problem, and if there really is a need to separate corp from app addresses, treat your app as the number one priority. Use gmail for your corp correspondence if you have to.
Because then people might wonder if I really did represent startup.com when I emailed them about a biz dev deal.
I agree with you regarding the trust/user experience issue with sending notifications from startupmail.com.
Well yeah, but I'd argue that that's better than having your users wonder if they're really getting emailed by startup.com or not.