What are the differences between the various versions of Stratego?
I can't speak definitively for all versions, but I can give you some information.

"Classic" Stratego is played with 40 pieces per side on a 10x10 board. There was a misprint in an early version that claimed Scouts could not move more than one space and attack in the same turn, so this is sometimes incorrectly cited as a difference between editions. There are also some differences in numbering among different versions; sometimes the highest rank is 1, in other cases it is 10.

As of early 2012, Spin Master Games has 3 different versions available. The 50th Anniversary Collectors' Edition has the original rules, theme (Napoleonic) and piece distribution, with some variant pieces available optionally. They also released a 50th Anniversary version that's a Toys R Us exclusive, which has the classic rules and theme, but no variant pieces. The third version is simply titled Stratego, and has a Sci-Fi theme, 30 pieces per side on a 10x8 board, and one of the pieces has a special ability to destroy an adjacent piece of any rank if it can correctly guess its rank.

Some retailers have some special edition exclusives, like Barnes &amp; Noble's Onyx Edition and Target's wooden box and bookcase editions. These are generally the classic version.

Several other sets have had pieces with special abilities over the years, including (but not limited to) Stratego revised (sometimes called Fire &amp; Ice), Civil War Stratego, Stratego Legends (which also supports up to 8 players) and Lord of the Rings Stratego. Most of these give most of the pieces powers, not just one as with the current version. (There's also Ultimate Stratego, which adds 4 player options, but I do not believe this version adds special powers to any pieces.) My understanding is that most of the rethemed versions have changed gameplay at least somewhat.

Of the variant rulesets, I have only played the LOTR version, and I will say that special powers do change the game significantly. In LOTR, the piece powers are asymmetrical, and I found them to be unbalanced. It also minimized the role bluffing plays and made the game more about getting the pieces with useful powers into the right positions - which could be a good or a bad thing. (I personally didn't like this change; it's also my main objection with some of the Stratego-inspired games I've played like Lord of the Rings: The Confrontation.) The piece distribution and board size was the same as classic in that version, so I can't say how the change in numbers impacts gameplay, though the consensus on BoardGameGeek seems to be that the smaller board doesn't change the feel of the game. The two rows that are lost are horizontal relative to the players, which means it shouldn't impact the way the armies interact. (If this is true, any of the special power sets should be acceptable, since you can always apply the classic ruleset to them.)