Use a single message is more efficient, but the max number of recipients for each single message is a parameter that change for each smtp server. This parameter is a limit imposed by the system administrator that manage the smtp server.
If you use the same server for all the e-mail, you can try to send a message with 10/50/100/200/400... to find the limit.
We use this approach in our e-mailing solution.
So, if the server has a maximum recipients number of 50; and we need to send the same message to 500 recipients, we create 10 message with 50 recipients each.
We use the BCC field to define the recipient list, because we don't want that the recipients know the e-mails of the other recipients.