PKlapwijk, as Stephen suggested, please verify your external sharing settings (for both your tenant and for the site you are sharing from). If that doesn't explain the problem, can you grab a screenshot so we can diagnose what is going on? Also, make sure the link you are sharing is one that will work for external users. If you create a link that only works for "people in my organization", but enter an external e-mail address, we will block you from sending it as it won't work.
AllanWith, sorry, I didn't see your question until just now! In the scenario you describe, the item won't show in users shared with me until they actually click on the link. The process by which we associate users with a link is what we call "redemption" and it can definitely feel a little complex.
When a user is "redeemed" onto a link, that is the moment in time when the user shows up in the "manage permissions" pane, when the item will show up in their "Shared With Me" view and when they can find it in Delve and Search. Conceptually, we want to redeem users onto a link whenever we (OneDrive/SharePoint) know that the user has the link. The case we want to avoid is when you copy an internal link for Bob but then choose not to send it, but the system exposes the item to Bob anyway. And of course it's even worse if we expose it to Alice too.
Today, this means we "redeem" a user at two points in time:
1) The user sends the link via OneDrive (i.e. clicks "Share") to Bob. Because OneDrive is responsible for sending the mail, we know that Bob will have posession of the link so it is safe to redeem him.
2) The user clicks on a link. If the user clicks on the link, they obviously have it and should show up.
There's more we want to do here to help it make sense (particularly when you copy links and send them around using other O365 apps) but that's all in the future for the moment. Hope that helps explain things!
Stephen Rice
OneDrive Program Manager II