So here's something interesting.
I'm using exactly the same control as you, I have built a sample that puts icons on the map.
In your sample, the icon overrides the labels on the map. In mine, the labels override the icons, causing them to disappear seemingly randomly, but they are really getting overwritten by labels on the map.
I've tried different Zindex's as high at 11 with no success. (your Windows Phone map icon is set to 5).
My sample uses a hub control and looks up the map control at runtime via its "Loaded" event handler, but other than that, I don't see a difference.
I'll also report this in the forums, but haven't seen anyone else with this problem, so I thought I'd just remark here since you have a sample that works and is for WP 8.1