Yes. Copyright covers exactly what's in their binaries, not anything you learn from their binaries.

I would argue that the opcodes in the binary are covered by copyright, but if you reverse-engineer those into C, that's your own creative work. Apparently Skype's lawyers did not see it this way, but why would they? If you're going to lie, you have to first convince yourself.

That's an interesting question. I'd be inclined to say no, but without precedent in court on this, it's tough to say. The reason I'd say no is that while pseudocode serves the same function as a "narrative spec" in this case, it's inherently not a new creative work -- it'd be easy to allege that it's a derivative work. I don't think you'll have an easy time convincing any judge that just because your 'code' doesn't compile or run, it's not still code and treated the same as, say, some C or Python.