An ex co-worker of mine had that happen to him. Him and his wife traveled to Austria in the 80s and were having trouble checking into a room in some rural town because it didn't seem as though they were married.
He was able to find an encyclopedia on a bookshelf in the lobby that said something to the effect of "In Iceland women do not take their husband's name when they marry". That resolved that situation.
There are also many stories of couples who were not allowed to get a hotel room together because they didn't share a last name.