I've not tried it myself, but this guy seems to have a pretty good solution to this common problem. You can view the source for it (without having to download the entire contrib project) here by looking under the WP7Contrib.Messaging folder for the single cs file that implements it. The project as a whole is intended for mobile applications (specifically WP7) but this custom Messenger implementation is really independent of that.
Basically, he makes a special Messenger implementation that "re-tweets" the last message for a given type signature every time someone new registers to listen for them. This way, the first VM can send its message, the second VM will get created (probably by your IoC container or whatever) and register to listen and immediately get the message that was sent before it existed.
Of course, this can have some problems with race-conditions. It relies on no other messages being sent for a given signature until the intended recipient has had a chance to receive it. In practice, though, I imagine this isn't too much of an issue. Particularly if you make good use of the target and sender parts of messages.