Do I have a MSc degree if I did the work but did not pay tuition? I have a BSc degree from a private university in Egypt. The university offered me a scholarship at the beginning of the program but that scholarship applied only partially to a subsequent MSc degree.

There's an overlap in the degree requirements for the BSc and the MSc, which means that the 5th year of the BSc is also the first year of the MSc. By doing research for 6 more months, the MSc degree is complete. The scholarship applied to everything but those 6 months, yet the tuition for that was very expensive.

Since I was a top ranked student, my dean said that if I did research at an associate research institute abroad he will ask the university's top management to  


officially enroll me in the program,
delay payment of the tuition,
and consider offering me a scholarship for the remaining tuition 


with one caveat: He will not know their decision until the very end of the program.

I took that risk, and successfully defended and submitted my thesis at the end of the program. While the university agreed to #1 and #2, my dean's attempts at #3 were fruitless. I have proof that I was enrolled as an MSc student and the university printed my degree's certificate but they will not hand it to me unless I pay the full tuition, which I can not.

My question is: Do I have a MSc degree or not? How should I address this on my CV/Resume?
No.

Unless your university is willing to provide proof that they granted you a degree, they didn't.  Listing an MSc degree on your résumé that your university is unwilling to confirm invites accusations of fabrication, which would be nearly impossible to refute and which could cost you your job many years in the future.

On the other hand, nothing stops you from publishing your thesis, or asking your dean for a recommendation letter explaining the unfortunate situation.