Garmin Express tells me that a map (Routable Cycle map of Europe 2018.10 can be re-installed onto my device (Edge Explore). I have already done this successfully (took > 2 h) but the Option still remains in Express. Is this normal?
No but occasionally it happens. You can either ignore it or try deleting the GarminDevice.xml in the Garmin folder on your device then reboot it so that file is recreated. Occasionally that doesn't get updated correctly and can cause the issue you're experiencing.