As far as I can tell, Majestic was the first pervasive adventure game. Its publisher EA advertised it as being The Game: the game – it would essentially "take over your life" for ten dollars a month (the reference is to the David Fincher movie). By blurring the lines between fact and fiction, Majestic was designed to induce high levels of paranoia. Players had to take clues from mysterious midnight phone calls, anonymous e-mails and faxes, and fake websites. However, it turned out few people were actually interested in paying for that. EA pulled the plug not long after its launch. The reason for its failure may have been that gamers were uncomfortable with allowing a game to intrude their daily lives. On the other hand, most players reported that the game didn't deliver on its prime selling point — the mysterious phone calls and e-mails were quite obviously part of the game. Regardless of whatever the reason was for Majestic's quick demise, it was an adventure game, although not recognized as one at the time. The gameplay focused completely on research and clue gathering. Majestic was much like an X-Files mystery, where players could peel off layer upon layer of a big conspiracy. Although Majestic was a little self-obsessed so to say with its focus on technology angst, it was the first commercial experiment in pervasive gaming.
In Memoriam is another pervasive adventure, but it's very different from Majestic both in its commercial success and its contents. Whereas Majestic's story dealt with UFOs and an all-encompassing government conspiracy, In Memoriam casts you in the role of a simple investigator, tasked with finding a serial killer. The game combines full motion video clips and in-game puzzles with web research and e-mail. In Memoriam's marketing campaign was decidedly more successful than that of Majestic. Instead of claiming that its pervasive gameplay would 'spook you out', it said it would draw you in and compel you to solve the puzzles.
In his review of In Memoriam, Jim Saighman explains that there's no apparent exploration or character interaction in the game, which leaves many in doubt whether In Memoriam is a true adventure game. Jim says that it is an adventure game — and I agree. In Memoriam is founded upon puzzle solving and story development, two essential components of adventure games. While there is no exploration in the sense of moving an avatar on the screen, the player is sent on a trail hunt through various websites (both fake and real ones). Although the browsing of a website may appear to be unrelated to adventure gaming, I wouldn't say it's very different on a conceptual level. The pervasive elements of In Memoriam are an integral part of the game world which players have to explore. You could even consider the e-mail correspondence of In Memoriam as an equivalent of character interaction in a traditional adventure game.
There is more pervasive gaming to be found outside of the game industry. As part of a guerrilla marketing campaign for the movie A.I., Microsoft and Dreamworks designed and operated a web-based game in 2001, known by its players as “The Beast” or “the A.I. Game”. The game was never officially announced, nor did it require any form of subscription. Instead, the movie's trailer contained a hint leading to the game, causing curious viewers to stumble upon the game by accident. Although no one told the players they were playing a game, everyone knew the events were orchestrated by an anonymous team of developers — the “Puppet Masters” — who updated the game every Tuesday.
A.I. was different from In Memoriam and Majestic in that it was inherently collaborative. Most puzzles in A.I. were so difficult that they required the involvement of the entire player community to be solved. Puzzles had players reading Göedel, Escher, Bach, translating from German, Japanese, and an obscure language called Kannada, decrypting Morse and Enigma code, and performing a range of operations on sound and image files downloaded and swapped between players. A.I. was, essentially, a collaborative multiplayer adventure game — perhaps even the first one. (E-mail me if you know of an earlier example.)
However, pervasive games can be taken one step further. Uncle Roy Is All Around You is an experimental location-based game that was funded by Microsoft Research and a number of academic sponsors, such as the University of Nottingham. During May and June 2003, street players — working alone, equipped with PDAs and wireless connections — explored the city of London in search for clues that would get them closer to the location of a mysterious Uncle Roy. Meanwhile, internet players could either collaborate or interfere with the street player's effort through an online 3D modeled map of the city. Street players had to make their location known at certain intervals in exchange for hints — dots on the 3D city map represented the positions of the various street players.
I'd known about Uncle Roy for some time, probably (but not sure) through locative academics such as purselipsquarejaw.org or angermann2.com. I hadn't made the connection b/w those types of games and immersive/web/nonlinear games, but damn if it ain't obvious.