He's not missing, he's right behind you, Weegee!
Mario is Missing! is a geography-based
educational game released for the PC in 1992 and
Nintendo consoles in 1993. It was the first game with Luigi as the main character, and the only one until
Luigis Mansion came out in 2001. The PC version is notable for giving birth to the "Weegee" internet meme, based on Luigi's
creepy sprite.
AVGN did a
review
of the game in summer 2009.
The premise is that
Bowser plans to flood Earth, and he sends Koopas to steal famous landmarks to help fund his operation. Mario, Luigi, and Yoshi travel to Bowser's castle to stop him. Mario enters all by himself and gets captured, prompting Luigi to go and rescue him.
Luigi progresses in the game by completing levels in Bowser's castle; each floor is guarded by one Koopaling whom you must defeat and contains a number of pipes which transport Luigi to a city containing Koopas. Once in the city, Luigi must collect the stolen artifacts. He must then find and reopen the landmarks by correctly answering three questions about them.
A sequel,
Mario's Time Machine, eventually came, which is pretty similar, but
WITH TIME TRAVEL!
Relevant tropes:
"...but they do have some spectacular hotels!"