I can't personally comment on the chance/timing of it subsiding on its own.
Are your servers being loaded down by the extra traffic? If the From address is random, I would think that your servers would drop it.
I think the only concern you have is being blacklisted by spam filters. Is this correct?
Every spam filtering system will have its own methods. I would also point out, that were domain-level blacklists in effect as you describe, major corporations (UPS/USPS/FedEx/DHL, for example), as well as major email services (Gmail/Yahoo), would have already been blocked, because (it stands to reason) that these domains would already have been filled out in the From area of countless spam emails. This is not your problem if your domain is blacklisted, nor is it Gmails problem if their domain is blacklisted by a spam filtering service. It would only be the problem of the spam filtering service that blocks you.
You should: tell the recipients it isn't actually from you, using SPF on your DNS servers to indicate whether the originating IP address (or block) is yours/legit or not (either white-list or black-list methods are supported). However, SPF is not fully respected, because if it was, there would be a large number of false positives due to the mistakes of a significant number of those configuring the SPF rules (things like hard-blocking legit addresses). This (if you avoid those mistakes) will not eliminate the problem on its own, but it may help the spam filters determine what to ignore, or it might help prevent a full fledged blacklisting of your domain.
You might want to make sure you know how to explain the situation clearly. Something like someone writes a random from address in your home town, to address of the recipient, and drops it in the mailbox in New York, or even China. The "return to sender" feature that the post office will provide, is completely ignorant of the Postmark (in this case, IP Address). There's nothing here that is hard to understand.
You could: report abuse to those ISPs who control the IP address blocks that are being used. I don't know if these measures are effective in actually stopping the abusive traffic, especially overseas, across multiple ISPs.