I take the position that "deceptively strong" means "not strong, but looks strong". That means that I disagree entirely with what Ed Guiness said; I would say that
"X is deceptively Y" means that X has less of the quality Y than it appears.
I have heard a lot of disagreement about this point, and while I write this, only one of the four other answers (Guffa's) also has this interpretation, and I disagree with something it says too; namely, I think:
"He looks deceptively strong" means exactly the same thing as "He is deceptively strong". That is, he is not strong but appears to be strong.
I explain my position with the following logic: "deceptive" is used in this way when used directly. The word literally means "not actually, but looks that way". For example,
The politician's concessions to the other party were deceptive.
(In such examples, politicians are always short-sighted, expedient liars, unlike in reality.) In other words, the politician gave the appearance of conceding their position, but in fact, had not changed their mind at all. Of course, there is potential ambiguity in that the politician might actually have had a genuine change of heart and was understating the degree of their acquiescence in order to keep face with their own party, so some context as to the expectation is in order here (that's why I used a lying politician). I will return to the manner in which this type of sentence is deceptive later on.
I can imagine an argument for the other position, that "deceptively strong" means "strong, despite expectations". This is undoubtedly based on the fact that one can write
He is, deceptively, strong.
That clearly means that he is strong and that you'd think otherwise. I don't think these are the same sentence, though. I could also say:
He is impressively strong.
He is, impressively, strong.
Imagine those both being applied to a wrestler: the former is a compliment, and the latter, an irony. Wrestlers should be strong; a weak wrestler wouldn't even be in a fight. It is not impressive when a wrestler is strong, and to say so is to imply, say, that he is part of a competition among unfit contestants. Another example:
This room is exceptionally blue.
This room is, exceptionally, blue.
The first one refers to the degree of the hue, and the second one refers to its presence. In the first, one is remarking on how blue the room is, and in the second, one is remarking that the room is blue rather than, say, white. In both cases, without the commas one modifies the adjective directly, and with the commas, one is actually modifying "is". Thus, the difference between
He is deceptively strong.
He is, deceptively, strong.
is that in the first, the manner of his strength is taken to be deceptive, and in the second, the presence of his strength is that which is deceptive.
One might argue that in "this room is exceptionally blue", the room is at the very least blue, whereas I am saying that in "he is deceptively strong", he is actually not strong. This happens all the time with adverbs, though:
He is apparently strong.
He is inadequately strong.
He is not strong.
In my opinion, deceptively is another one of these words that inverts the sense of an adjective.
The other interpretation extant at the moment is pageman's answer, which holds that deceptively means there is more than meets the eye. It's true that in a deception, there is always something else going on, but that something is always in defiance of appearances. One would not say,
The richness of this New York cheesecake is deceptive.
because that would be like saying you are deceived by how rich said cheesecake is (a New York cheesecake, by the way, is pure cream cheese and looks it). It is hardly possible to expect a richer food. If you did make that statement, it would be a criticism of some kind (what kind depends on your expectation; perhaps you expected to like the cheesecake because you like rich foods, but you thought it wasn't that good).
If I wanted to indicate that there was more than meets the eye and that the difference was a positive contribution, I would say:
He is unexpectedly strong.
This conveys the impression that Ed Guiness describes.
It may appear from this example that I'm endorsing the interpretation of deceptively to depend on the context of expectation, so that in fact, a skinny guy could be "deceptively strong" simply because you expect him to be weak. This appearance is because the sentences
He is deceptively strong.
His strength is deceptive.
seem to mean the same thing. These phrases are, however, deceptively similar, because in the second one, "deceptive" ambiguously refers either to his being strong or to the strength itself.