You could make this work if you took into account the time the call and voice mail were received. You could even treat them as a "conversation" kind of how gmail does.

The thing that strikes me as odd, is that Apple doesn't do this. This problem and work-around were obvious to me the first time I got a voicemail. And Apple doesn't often make thoughtless mistakes like that.

It makes me wonder if AT&Ts voice mail system just isn't giving them enough information to match the records reliably.

(E.g. If the voice mail record doesn't distinguish between the origination number and the callback number, trying to match messages to missed calls would be inconsistent.)

It wouldn't have to be much; just enough margin for error to make the system a little unreliable. Because I can definitely see Apple opting for 'weird, but consistent' over 'inconsistent', even if it is only rarely inconsistent.