However, I think you overstate the significance of phonology. Many native English speakers struggle to understand Glaswegians; partly, that's lexical, but mostly, it's phonological. It doesn't mean that it's hard, though, just that the listener is unfamiliar. An American dropped in Glasgow would soon learn to understand the locals, I feel sure.
You say that you've lived in Denmark for two years but still struggle to parse spoken Danish. That seems like slow progress: would it be fair to assume that you spend your time mostly in an English-speaking environment? I ask because I'm trying to work out to what extent Danish pronunciation is hard, and to what extent you just haven't had much exposure.