Ok, after some testing, I think Moeba is right when he said "Maybe it's because the enemy needs a turn to recognize that it's dead and its speed was so low that we got another turn before them?"
Not only does this happen sometimes, although infrequently, with normal speeds of slightly over 100, but as your speed increases, the chance of this happening increases as well. With over 300 speed, you can usually kill a monster three times before it is removed from the map.
Similarly, the problem with bringing them upstairs appears to be caused by the same. Supposed you spend 1000 turns on level 1 of the dungeon. Areas seem to keep track of their elapsed time, and when you leave the level, time does not pass on other levels. So when you descend to level 2, it is generated at turn 1000; then you spend another 1000 turns on level 2 and end on the upstairs to level 1 with a monster next to you. You go upstairs, and the monster follows you... the next turn the monster is set to act is turn 2001; but the time on level 1 is still at turn 1000, so the monster won't get its turn for the next 1000 turns, so it will neither move nor be removed from the map if it dies. You can test this yourself rather easily, and it always happens that the monster doesn't move or is not removed after death for the same number of turns as you spend on the other level of the dungeon.
Turns of course is just a measure of time and depends on your speed.