You probably did consent, it would be somewhere in the terms and conditions you accepted without reading them.

This may be against GDPR in Europe, but may not, because everyone they are suggesting has agreed to Skype's term at some point.

My understanding was that you can't sign away your GDPR rights just by accepting a ToS.

Correct - there has to be a clear indication that you are consenting. It can't just be hidden away in a 60 page document in a statement that says "I consent to being tracked, etc".

AIUI GDPR requires explicit consent, not just "we tricked you, ha ha" consent.