The missing information in the pm_recipients table would explain that.
Without that info as well, the pm data would be lost if you tried to fix it.
I am not as good at perl. But you could do a redirect to a php script, that would connect to the database and find the message that had the time stamp that was in the url and then redirect them to the topic.
Currently I am in the middle of oscon (I am typing from the show room floor right now), so I don't got time at the moment to program something up that might work.