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.

Copyright doesn't just cover "exactly what's in their binaries", because of the derivative works statutes. If you translate a book from English to French, the resulting book is still under the copyright of the original author; the same goes for taking disassembly -> decompiled C.

Something becomes a derivative work when excessive amounts of the source material structure comes from a copyrighted work. If you reverse engenear a program create a spec and have someone else code to that spec then copyright does not cover you.

You could create an original novel that was not a derivative work by taking once sentience from every book in a library and trying to create a meaningful work of art from it. Doing the same thing using a single book would probably not fly.

Yep, that's why the concept of clean-room reversing exists, to get around the derivative work concepts. It's not the only option, but it's probably the safest.

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.