I and Pinkunicorn have discussed this a bit. I will post my conclusions.
Since the parts belonging to Akrotiri and Dhekelia doesn't belong to the country Cyprus, I would say that they geocaches there has the wrong country. Due to that fact, Project-GC is assigning them wrong regions. When no matching region is found for a geocache, Project-GC uses the closest, if it's close enough. I do not remember the max distance allowed for that fallback. This fallback often helps in cases where geocaches are plotted in the ocean, but also lakes and some other odd cases.
I see three different solutions to the problem, which I will present here.
1) Make HQ change the country to a correct one. I am not sure if the correct would be United Kingdom, or United Nations (which isn't a country, not even in the Geocaching-world).
2) Consider these areas as a part of Cyprus. My understanding is that they aren't actually a part of the country Cyprus, but at least they are a part of the island that's generally called Cyprus. Google Maps seems to consider the parts as another country, I can see a country border on their maps.
By considering them as a part of Cyprus we should then add two more regions to Cyprus. Might not be politically correct, but might be a decent alternative. Today's solution obviously isn't correct either.
The problem here is that I can't find the polygon data for these areas in OpenStreetMap. I can see on the map itself that there are borders, but I can't find where to extract the data. Without the data, we can't actually do this.
3) Don't care. Not the biggest issue.
Solution three is obviously the easiest, and right now it seems like the solution we have to go for. I would however prefer solution two, but without the polygon data, there isn't much we can do.