Well, we don't use the verb stannar like you use stay in English, i.e. in order to mean 'live somewhere for a short period of time'. But we do use it to mean 'be somewhere for a short time', 'make a stop somewhere'.
So I can't really think of a context where de stannar på ett nytt hotell would be likely to be used. But Han stannar på hotellet medan hon går ut och äter lunch 'He stays in the hotel while she goes out to have lunch' is fine, it just doesn't mean live.
I'm not sure I understand what you mean, could you rephrase that question? What did you put exactly? You don't have to include staying, the sentence has several accepted answers. For instance you could say they're living in or at a new hotel if you prefer that. You can't just say that they are at a new hotel of course, since the Swedish sentence says that they 'live/stay' there.