Mail.app has these issues consistently, across versions. Which is a real shame, because UX-wise it is a really fine mail client.

Also, threading algorithm changed slightly in Mavericks, leading to many more mistakes than ever before.