Notifications for emails deleted by other clients will only disappear once K-9 Mail learns that the message has been deleted. If you want this to happen in a timely fashion, enable Push. If you only use periodic polling, the notification will be displayed until the next time the folder is checked for new messages.