Contacts with access to no mailing groups cannot do search based CiviMails

If contacts have no group access & no previous mails they get this message when trying to do a civimail

"To send a mailing, you must have a valid group of recipients - either at least one group that's a Mailing List or at least one previous mailing "

However, that seems to pre-date the introduction of the ability to do a civimail from a search