There's one thing I would like to clarify. If let's say there's a downtime of 10-15 minutes during my migration to VPS SSD, and that I use private nameservers (ns1.mydomain.com, ns2.mydomain.com), what will happen if someone sent me an email coincidentally during that downtime (e.g. using their Gmail, Yahoo, Hotmail account), will they immediately receive "No MX or A records for mydomain.com" hard bounce type of error?
Typically; they'd wouldn't receive a message at all -- it would be delivered to the old host/server that you were migrating away from.
DNS Servers would still have the old addresses of your private nameservers cached; and as long as that server is still be online during your migration, mail would be still getting delivered to the old server.
When you change your nameservers, providing that the old server is still online -- mail would still be delivered until Global DNS Propagation has occurred and then at that point, mail would be delivered to the new server based on the nameserver IP's and the domains that utilized them.
The best way to avoid the above scenario; would probably be to migrate the accounts over and if you have control over the DNS Zones for each of the domains, manually set their MX records/A records to point towards the new server on the old server.
That way, during the migration process the only thing you would probably have to do is a final sync over for any missing emails that occurred while DNS propagation was happening.
The only way that you'd receive a bounceback is if you had a period of time where you had the nameservers being used have non-respondent IP's; but that ususally isn't the case in migrations.