Office 365 Guest Accounts - Sharing vs SharePoint Permissions

More people are beginning to the use the share functionality in our SharePoint Online instance instead of the traditional adding the users to the permissions of the site. One thing we've noticed is, sometimes when a new guest user is added through the share button, they never get any notification email and when they try to access the link, they'll get a user not found error. When this occurs, I'll just have them add the user to the permissions and it works fine. 

Why is this happening?