Ah, the X does not move to the trash, it deletes the message right away -- which Gmail treats as removing the current label from the message, but keeping it in [Gmail]/All mail.
And if you're looking in the [Gmail]/All mail folder, the message won't be deleted, Gmail will keep it on the server as the "last resort" place.
The server behaves (for IMAP) as if it's deleting the message, then on the next mail check it's still there, and even the "deleted" flag is cleared. In other words, the server lies to the app to make All mail special.
This only applies to the All mail folder, though, as far as I can see.
You can change the default from the X to "Move to deleted" in the account's Options and Folders.