Solved! Go to Solution.
The share link you posted shows that your map is part of an organization called 'mapport'. If you're signed in with an account that is part of that organization, the links you share will be to your organizations area of ArcGIS Online. However, I think that it's likely your organization does not have anonymous access enabled, so Explorer Online cannot access that URL which is part of the organization. Seeing as you shared the map with everyone on ArcGIS Online (publically) you can sign out, and then find the map and open the Share dialog that way - this time the link will have a URL to the map without going through the organization - for example http://www.arcgis.com/explorer/?open=3f129d8baff34157899f1683f7fea456 - anyone can now open the map from that URL without being signed in.