In Messages, you cannot up and down arrow through the table of conversations. In most OS X tables, you can simply up and down arrow with no VO keys, and interacting is unnecessary. In Messages, this is not the case, and pressing down arrow by itself (with Quick Nav off) will move you to the text field to write a new message.
Bug First Encountered
How often the bug occurs
Interact with the table, and use the arrow keys in conjunction with the VoiceOver keys to navigate. In most tables on the Mac, not only are the VO keys unnecessary, but you generally don't even need to interact in order to move by row or expand/collapse items.