I have made progress, but have traded one error for another.
I use Toolset Access to manage user permissions on pages and posts, and I had the Front End PM message page restricted so that only Members (a custom role) could view that page. I believe it was Access that was generating the “Page Not Found” error, not Front End PM.
As a test, I temporarily removed the page restriction in Access, and now I no longer get the “Page Not Found” error. However instead I get the correct messages page, but with a red box stating “You must login to view your message.” Is this correct behavior for Front End PM? In your initial reply, you indicated that I should see a login link, then be redirected to the message after successful login.
If you follow the link I sent in my last private reply, you will now see the new behavior.