I would expect this to mean you lost it due to a fire or an environmental disaster, but your last examples could also work.
If you drove past the house you were looking for, you would say "Vi har kjørt forbi huset" = "We have driven past the house". I don't know if there's an equivalent word in Norwegian for 'missed' in that context, so you would probably just phrase it like that.
This is probably just my twisted brain, but I interpreted the English sentence as being "we mislaid the house somewhere and can't find it again". Now while that's obviously a somewhat improbable situation, is that a possible meaning of the Norwegian if you're talking about e.g. a piece from a game?