When I delete a message from my POP3 mailbox, the CountMessages method still returns the same number of messages. Is this a bug?

No, it’s not a bug. When you delete a message (by calling the DeleteMessage method), the message is not deleted yet, but marked as deleted. It will be deleted as soon as the connection is broken.