It's a little odd that you mention this in the context of message order. Quoting you:
As far as I understand, the order in which non-blocking point-to-point
MPI messages (Isend and Irecv) are received is consistent with the
order in which they are sent.
It's worth pointing out here that MPI only guarantees that matching messages between processes will be received in the order they were sent. You really don't want this type of ordering to change, because it makes your code more understandable and takes a huge burden off of you as the application programmer.
However, if you sent messages with different tags, that changes the matching criteria, and you could easily receive the second before the first. See the second example in the relevant portion of the standard for details. I hope that if you have two pieces of your code sending simultaneously that you're already separating the coarse and fine messages using tags, and not trying to implement some protocol of your own on top of message ordering. This is second nature to most MPI programmers I know.
Anyway, assuming you're doing that, you're probably concerned that high-volume fine-grained messages are going to clog your network when you want to send the coarse ones. My general advice on this is that if it's not a performance problem that you can actually measure right now, then you really shouldn't bother addressing it yet. You seem to confirm that it's not an issue yet in one of the comments above.
One possible solution you might consider would be to use a non-blocking collective (NBC) like Bcast or Barrier to notify everyone that the coarse phase is done and ready to send its solution. In all likelihood, the NBC traffic isn't going to get prioritized, but notified processes can at least stop sending gobs of fine solutions until the coarse sends are done. NBC's will be in MPI-3 or you could try using libNBC if you can't wait that long.
Again, though, this seems like a lot of work for something that doesn't sound like it's a performance problem yet.