How many times is OK to register for a PhD program? I started a PhD program few years ago. My first PhD supervisor decided he wanted to quit university and stopped supervising PhDs (he was 70 years old). I lost about a year trying to convince this supervisor to continue, and another year trying to find another supervisor when he quit (he pretty much left all his PhD students in the air). 

I transferred to another university, but nobody counts the missing years and I should finish in few months. The condition put by my new supervisor in order to be allowed to present my thesis was to come up with at least 2 new contributions in addition to my previous contributions (I have published some papers with some contributions, but many of them were group research and this supervisor said that only 2 or 3 of them really count as mine).

Now the problem is that during the last year I have worked a lot both at the university and at the PhD, but only during last weeks I started to have some ideas about what these new potential contributions could be. Considering the lack of time, there is a high chance that I won't finish on time (due to the regulations from this country you have to finish in 5 years, nobody takes into account the fact that you lost several years with other problems like replacing your PhD supervisor).

I'm not a lazy person, but first time I really had no luck, and with the second supervisor it took me a lot of time to play in the league he wanted ... Basically all articles discussed with him about Machine Learning were from MIT, Carnegie-Mellon, etc. Essentially I had to spend about a year and a half to get my knowledge to the level where I can design new algorithms or create new things that would get accepted to top journals reviewed by people from these institutions.

Of course, I can register again for the PhD, take the exams again, and present my contributions in a new thesis. The problem is when I will add all these years it will result a large interval for Europe: 7-8 years, instead of 4-5 years. My question is this: how will a potential future employer from both Academia or Private Company look at this time interval? Is it ok to try 2-3 times to finish your PhD? Will the fact that it took to long finish the PhD affect my career?
The fundamental issue here is that your first advisor left academia altogether—by retiring before his students were done. This is an awful thing to do to the people one is supervising—leaving them completely in the lurch in such a manner is unacceptable behavior. The advisor should not have taken on new students if he was planning on retiring. 

As a result of this, it is obvious that some allowances for this will need to be made. The way to signal this is through your CV: list both advisors, including the dates for which you worked with them. If your first advisor is well-known enough, then this will automatically clue in others about what happened. 

Overall, though, so long as the time required isn't too unreasonable for your discipline, an extended stay in graduate school isn't problematic. However, if you have mitigating circumstances such as these, it makes such problems a lot easier to overlook.