The Maze is used by many ad agencies as we can see here: http://www.coloribus.com/admirror/maze/

Why not improve on that and take a QR Code and explain inside the QR Code

• either what the QR Code is all about and how to download the QR Reader
• or what the company will offer through the QR Code. An example could be that the QR Code typograpical elements explain the rules of the game being played by the QR Code.
• Last but not least, think hard about the similarities between Mazes and QR Codes. Not only the obvious visual ones.
  Quotes:
  

  Myth says that the labyrinth was solved with a clewe of twine - Old English for "ball of string". So a maze is the solution to a pattern-making puzzle which was solved by geometry - which means ground-measurement. This is the origin of our word clue.
  
  [...] The idea that there was always a way to find a path seems to have developed from the symbolism of the labyrinth. Mathematicians call finding the best path in a maze critical-path analysis. CPA can find the cheapest route for telephone-calls, design the electrical paths of circuit-boards, or reduce the cost of road-trips. Computer-programs which do critical-path analysis are called autorouters. Autorouters help miniaturise and cut the cost of electronics, and have been a major factor in the development of Information Technology. The first autorouter was tested on a map of the maze at Hampton Court Palace about 35 years ago.

In this last regard, the QR Code on the LOST ad makes perfect sense.

See also:
Olga Kisseleva's Maze/QR project

Image: [altogether] digital

Ellie writes:

Hopefully, a tool intended to generate buzz about Lost Series 4 can also contribute to the rise of the quotidian QR code in this country. They’re fantastically versatile little things and a good example of technology doing what it’s supposed to do: streamline our lives a bit.

Ellie the QR Code is on the rise globally - right now Brazil is going crazy about them, France and the US are catching up:)