The solution as I found recently, is to use the 2010 workflow to send the email as it is not bound by the restrictions. The 2013 workflow is in only sending to users known by the tenancy (i.e. those with accounts).
In my case I did all the main bulk of the workflow in 2013 with loops and all the nice new features, then used a really simple parameter driven 2010 workflow which just took an email address and a title and body for initiation parameters and used those to form the email message and 'to' address, then set the 2010 workflow to not start on new, update or manually.
Then my master 2013 workflow used an action of Start Workflow to start my 2010 email workflow, passing in parameters from the list of other variables as required. This works really well even in my scenario where i'm looping through a list of 400 people with a web service call and emailing updates to them.
The solution is akin to something like C# where you have a simple method to do the email task and call it from various places with a few parameters. Hope that helps!