name server down --> mail can not be routed ?

Hi all,

I got domain example.com

with name server ns.isp.com

;; AUTHORITY SECTION:
example.com. 900 IN SOA ns.isp.com. root.isp.com. 2016030702 10800 3600 604800 10800

and mx record
0 vps.example.com
20 vps2.OtherExample.com

Also I set backup name server at isp's managament panel as ns1.cloudns.com

Everything worked fine till today when ns.isp.com went down. I tried to perform
$ host example.com
from different vps servers and one of them had cached information, but other didn't and just answered 'domain not found'.
Now ns.isp.com is up again after few hours
So I tried to send email to myself to user@example.com from different exteal mailboxes and as I can see, some of them already know that I'm online again, but other still think that my domain doesn't exist:

4.1.2 <user@example.com>: Recipient address rejected: Domain not found

So what should I do to prevent this? As I can see, my ISP doesn't provide backup dns and my try to use free dns ns1.cloudns.com didn't help.
The worst is that it seems I loosed emails and my backup mx record didn't help too.
Please advise.
Thanks ahead.