Just to clarify, if you mail the individual address, it works... Is that by selecting the contacts from the list, or entering the addresses soome other way?
If you expand the distribution group (by clicking the +sign next to the group) do the addresses work?
Some of the issues I could understand, but #5 where it says the mailbox does not exist may indicate something is wrong with the address itself.
The other idea I had was depending on the number of addresses you are trying to reach in the same domain, domain maol host might be cutting you off after a specific number, thinking that your server is sending spam.