My European bought Edge 1030 Plus came with "Routeable Cycle Map of the United States" and "Routeable Cycle Map of Europe" pre-installed.
However, Garmin Express (even the latest version 7.1.1.0 just released) was not correctly managing the maps.
The maps were showing as installed when clicking "Map Details" but when clicking "Manage Maps" they were showing as not installed and that "There is not enough space available for this map". The memory usage bar at the bottom was showing only "other" (green).
My workaround was to reinstall the already installed maps ("Map Details" / "Options" / "Reinstall Map").
Not the most "elegant" nor "efficient" solution but it worked. The maps are now showing as installed (and can be deinstalled) and the memory usage bar is now showing other and maps (and the total memory used has not noticably increased).
In terms of actual files on the device, reinstalling the maps has deleted four files (gmapprom, gmapprom1, gmapprom2, gmapprom3) and created 8 new files (D4677150A.gma, D4677150A.img, D6016040A.gma, D6016040A.img, D6017040B.img, D7557040A.gma, D7557040A.img, D7786020A.img) which leads me to think that it was more than a simple Garmin Express problem.
Hope this helps others facing the same issue.