Wow thanks for clarifying. That is absolutely deceptive. The UI never mentions that, but I found some support docs that do. I imagine the majority of people deleting messages aren't aware of this...
Your SMS, IRC, etc. messages are stored locally. Your Facebook messages get loaded from Facebook.
and fair points about email... I had assumed this worked like other parts of Facebook, which doesn't seem unreasonable given they control the whole stack. (and they did shut down their old XMPP gateway awhile back)