Mail (SMTP) is a store-and-forward system. For example, if domain X.com has a single mail server, and it begins to fail (server problem, problem in network in front of server, etc.), then server trying to send mail to that domain will not fail -- it will instead notice the problem, store the message, and attempt to retransmit it later.

Thus, any extended problem in communicating with your mail server can easily result in a "burst" of mail later, when a bunch of different external servers notice that your server is working again, so they immediately transmit all the mail they have stored up for your domain.

Typically, there's a limit on how long mail servers will retry (e.g., 1-3 days) before giving up and sending a bounceback to the sender to notify them of that the mail could not be delivered despite multiple retries over time.

Without direct access to your mail server, it would be hard for you to narrow down exactly what is failing when/where.

Seems like it's all in hosting company's hands again then.