I have had this same problem happen on two PCs in the last year...the difference is we're using Lotus Notes as our e-mail client. It was taking the user to somewhere in the vault that they had received a Notification for in the past, but not the folder location for that specific Notification. I double- and triple-checked, and sure enough, the documentid info was correct...it just wasn't taking the user to the correct location in the vault. Could forward the Notification to another user (with proper vault access) and the links worked perfectly fine for them. I could send a different Notification from a different user to the user experiencing problems, and that user experiencing problems with their Notifications...? They had trouble with the other users' "good" Notifications as well. So it seemed to be PC-specific in our case.
Then I noticed something strange...if I brought up Windows Explorer on its own, and clicked on the vault name in Favorites, it would take the user to the top of the vault as usual, but only for a split second...it would then dive into that seemingly random location in the vault, just as if they had clicked on a Notification link that was taking them to the wrong location in spite of a good documentid.
I wrestled with this for a few days on-and-off the first time. Our VAR was at a loss to explain it. Out of sheer boredom, I opened a new Windows Explorer session, and instead expanded the C:\, then expanded a few folders down, *then* clicked on a green folder to see what was in it. Of course, that worked okay...and miraculously the next time I clicked on the vault Favorite, it went to the top of the vault and stayed there. When I went back to the Notifications and tried them, they all worked perfectly. Diving in to the vault location from C:\ must have cleared out some cobwebs.
Months later, when another user was having the same errant Notification problem, I checked the vault Favorite...same behavior. Dived in to C:\, clicked a folder, and the cobwebs cleared, and everything went back to normal for the user with respect to Notifications.
As much sense as that doesn't make, give it a try!