This is clearly a bug. The documentation in main.inc.php says:
// When a Trash folder is not present and a message is deleted, flag
// the message for deletion rather than deleting it immediately. Setting this to
// false causes deleted messages to be permanantly removed if there is no Trash folder
$rcmail_config['flag_for_deletion'] = FALSE;
Regardless of how this setting is configured, if I log into an E-mail account that does not have a Trash folder whose preferences have not been previously changed, I can send and receive E-mail, but when I try to delete a message, it briefly disappears but then I get a warning box that says "/!\ Could not move the message" and the message reappears as before. This bug can always be reproduced. Set the home directory of a test user with no IMAP folders to be non-writable so that a Trash folder cannot be created, then set the 'preferences' field in the 'users' table to NULL (the default when you create a new account).
Also see related bug #2...
(p.s. permanently is spelled incorrectly above)