Can be replicated by limiting countries by store and then switching store and looking at "/customer/addressadd"
In the Admin, clear the cache and this resolves the issue.
We have a 2 Store site, with just 1 country per store. When a user goes to any page which displays a Countries drop down, it caches that list of countries for that store. Go to the other store and you get the wrong list of countries. Clear the cache and refresh and you get the right list of countries. Switch store again and you now see the countries from the other store.
The bug is on line 100 of CountryService.cs where store is chosen within a caching code block and is not used in the cache key.