Hey guys - I work on Timeline here at Facebook and just wanted to chime in here. I've looked into a bunch of cases today where people were concerned their messages were showing up, but as has been pointed out in many places (e.g. techcrunch), there was no privacy violation here.
If you've kept your old emails around (woohoo gmail!), one thing you can do is go back and look for the notification email you got for a particular post that you suspect was a message. There's a date search widget that makes this easier. I suspect you'll find it was a wall post.
Another thing to note (for those that follow our technology), is that the backends for these two systems are entirely different. The messages backend is hbase-backed, designed for real-time communication more than history. The timeline backend is MySQL / C++ backed. Migrating data from hbase to MySQL would have to take months of effort.
I know that even though there was no bug here, this can be an alarming experience to see old posts surfaced like this. We're working on ways to make this interaction clearer so people aren't so surprised in the future. That said, please rest assured that your inbox is not on your timeline.
Buy a Shirt