Mossflower is a young adult fantasy about some mice on an adventure. The two main characters are routinely described as “the warrior” and “the thief”, so you don’t have to look far to find the D&D roots here.
An interesting difference between mice and human heroes is that mice don’t have the sense of entitlement that comes with being on the top of the food chain. Humans expect to be able to kill any monster, even dragons; but there are a lot of predators that mice, even mice warriors, flee.
At one point, the rodent heroes fight a crab. They’re forced to flee because the crab’s shell makes it impervious to their attacks.
Obviously, Mouse Guard is the appropriate system to model such a battle, but as a D&D battle, it could still make a memorable encounter. A fight with a creature with an unreasonably high AC could potentially be more like a puzzle than a traditional battle. How can the PCs triumph if they can’t hit? The AC would have to be very high, though: if it were just, say, 5 points higher than average, the PCs probably wouldn’t change their strategy. They’d just bang against the creature for turn after turn, missing on a die roll of 15 or lower, and blame the DM for a boring encounter.
Furthermore, in 4th edition, there are a lot of non-AC-targeting attacks; most parties could probably take out a creature just with these. This wouldn’t constitute a puzzle encounter. It would just be a way to make the fighter feel useless while the wizard felt awesome.
To make this into a puzzle encounter, let’s take a page from video games. Traditionally you can only hit armored opponents when they open their eye (and blink red). Perhaps the LAZER CRAB has high defenses (requiring a natural 20 to hit) during the PC’s turn; but it opens its eyes briefly to shoot its CRAB LAZER during its turn. Therefore, the trick to the encounter is to ready an action to attack when its eye opens.
I’d give the crab this unconventional set of actions (all minor actions):
FIRE CRAB LAZER: Minor action.
OPEN EYE: Minor action. While the crab’s eye is open, it can fire its CRAB LAZER.
CLOSE EYE: Minor action. While the crab’s eye is closed, its defenses are very high.
For the first half of the encounter, the LAZER CRAB uses its actions to a) open its eye, b) fire LAZER, c) close its eye. Once the PCs figure out the readied-action strategy, or when the crab becomes bloodied, the crab suddenly becomes more dangerous: it stops closing its eye and fires 3 CRAB LAZERS every turn.
Another encounter possibility: the ARMORED SUIT OF ARMOR. It can use its shield as an immediate interrupt, raising all its defenses by +10 whenever it gets hit. Therefore, it can block one attack per turn. The PCs may be able to play interesting tactical games with the DM, trying to draw the shield block with low-damage attacks so they can hit it with their encounter powers.