This has happened to me a couple of times, and it is a major problem for me.
i have about 10 accounts setup in aquamail, all are set to IMAP, and all of them are set to "hide in the app, keep on the server". i double checked and triple checked them.
on 2 random occasions, when i deleted the emails from my phone, i went to work later in the day or day after, and opened outlook, they are not there at all. logged into webmail, and they are not there as well. yet i've been using k9 mail (which i no longer use) for more than 3-4 years, and never had this problem.
this is a big problem, because i normally delete all msgs from my phone as soon as i see them, and i keep the important ones which i need to reply to later.