The thing I looked for the first and, hehe the only time

I didn't get this to work was that I really didn't get all the language files in the correct directories.
eg. look into one folder of let's say ~/administrator/components/com_virtuemart/languages/common/ and see if you can see the file danish.php in there.
I'm setting one site up that also is gonna have Danish in there and as I copied the files into those directories and I changed the language in the Joomla admin, it just worked.
I use the latest bundled version.
If it still won't work I think there might be a problem with the entire installation, maybe the Joomla installation.
If this is your first installation, just remove all files and just try from the beginning, cos in my first time... DOH!!! did I do it wrong, but since it still was "internal" like for me only, I removed all files and tried again from beginning.