Seems I've learned this the hard way today, and after a quick search I found this:
https://bugs.maemo.org/show_bug.cgi?id=10435
Although it says "fixed", so I'm confused...

Namely, I checked my email on N900 today (with its default mail client), and after I got home I didn't get those same messages on my computer. I use POP3 on N900, and "leave messages on server" is checked on all accounts.
It used to work fine a few days or weeks ago, but back then I deleted messages from N900's Inbox only after retrieving them on the computer (whereas today I deleted them right away - so it sounds like POP3 acting IMAPish in this regard ).

So I suppose I should be more careful with this?

Can we assume that you have PR1.3? (the bug was (supposedly) fixed there).

Have you installed CSSU or any non-standard modest versions?

Yes, I have 21.2011.38-1 (November's official), and a few days ago I installed latest stable CSSU (21.2011.38-1Smaemo3, 30.03.2012). I didn't tinker with Modest, unless the CSSU installation changed it. CSSU is one of the things that's different between "now" and "then", the second one is that I didn't delete messages in Inbox when I first tried POP3 here at least not until I downloaded them on the computer.

I have the same problem,
There was a bug on PR maemo but was fixed with the latest PR 1.3, now the bug is back with CSSU stable and testing.
I suggest not to delete the emails from your N900 before you download them on your pc, you can view but if you delete them from your device then will be deleted from the pop server too.

We have to report the bug. (I already made a comment on CSSU stable & testing about above a wile ago, never filed the bug, my bad)

Edit: If you have a hotmail, hotmail live, yahoo, gmail you are safe there as they have setup a security feature for mobile devices just in case you delete the emails accidentally your emails will be under "deleted folder -pop mail" but if your emails are from your pop 3 internet provider well... then you will lose them.

New bug report opened with reference to the old one, to view, vote for faster problem solving see bug report 12604 here

Edit: apparently is a duplicate see bug 12285

There is a fix for Modest for the above problem and another 2 bugs reported for CSSU stable and testing thanks to freemangordon pointing us to the right direction, please follow his instructions on this post.
After updating your Modest to the latest version I suggest to disable/delete merlin1991's application catalogue unless you really know what you are doing.

Is there any special reason why the fix hasn't "graduated" at least to extras-testing yet?

The new CSSU-T update was supposed to be out several days ago, but there is some problem with the repos. Hopefully it will be sorted out in a couple of days.

Will the fix go into the CSSU-stable as well? (and until then I "pretend" my N900 mail client is like IMAP when it comes to deleting messages)