Help on the Net pointed towards it being a problem with Local Distribution lists and advised setting up a list in AD instead of using a Local DL.
A quick guide to solving the issue via their solution is here: http://smtp25.blogspot.com/2007/04/500-non-rfc-compliant-responses_18.html
However, it appears that in my case, the addresses that failed had the following in common:
1. The address existed in AD and in the local DL.
2. The local address had a NAME field that only partially matched the one in AD. For instance, in the Local DL it would be “John Doe” whereas in AD the name would be “John Doe – Home”
It’s interesting to note that an address in the Local DL had a name drastically different from the one in AD, but the same email address and it didn’t fail. Also, other addresses in the Local DL matched entries in AD and they did not fail either.
I opted to delete the entries in the Local DL and add them back from the entry in AD. Will monitor next mailing to see if the addresses fail or not.