Out of curiousity, Cafeman, have you played The Colossal Cave (the first text adventure)? I understand it was Warren Robinett's inspiration for Adventure. I suspect that you have indeed played it. The game featured a troll on a bridge like you were talking about, and some of your stolen items would be placed in a maze (though it was a pirate that stole them). Anyways, if there were any source I'd take ideas from (other than 2600 Adventure) it would be from this game. For example, you might consider having the player retrieve multiple treasure objects to win (instead of one) in some of the modes.
As for whether the bridge should be in, I would like it if it was... however, if you find a bridge like the one in the original game complicates things too much, I suppose you could have it only let you cross over non-wall barriers instead (like moats, rivers, pits, etc.) so as to be more like a normal bridge.