Rulers
Europe's longest-serving head of government (as opposed to head of state), Cardinal Sodano of the Vatican, is to retire in September. He had been doing the job of Secretary of State for almost exactly fifteen years, since 28 June 1991, and had held the post in an acting capacity from December 1990.

There are six other Prime Ministers in Europe who have been in office since before 2000:

• Guy Verhofstadt of Belgium, since 12 July 1999
• Mikuláš Dzurinda of Slovakia, since 30 October 1998
• Bertie Ahern of the Irish Republic, since 26 June 1997
• Tony Blair of the UK, since 2 May 1997
• Göran Persson of Sweden, since 22 March 1996
• Jean-Claude Juncker of Luxembourg, since 20 January 1995

Also one could make a case for three of the seven members of the Swiss Federal Council, Moritz Leuenberger who has been on it since 27 September 1996, Pascal Couchepin since 11 March 1998, and Joseph Deiss since 11 March 1999 (Deiss is retiring next month).

That's heads of government. There are no less than fifteen Heads of State in Europe who have been in office since before 2000. (Again, one can make a case for including the Swiss.) They are (with those who actually wield significant power in bold):

• Vladimir Vladimirovich Putin / Владимир Владимирович Путин, President of Russia, since 31 December 1999
• Vaira Vīķe-Freiberga, President of Latvia, since 17 June 1999
• Robert Kocharian / Ռոբերտ Քոչարյան, President of Armenia, since 4 February 1998
• Mary McAleese, President of Ireland, since 11 November 1997
• Ólafur Ragnar Grímsson, President of Iceland, since 1 August 1996
• Jacques Chirac, President of France (and therefore also co-Prince of Andorra), since 17 May 1995
• Alexander Lukashenko / Аляксандар Лукашэнка / Александр Лукашенко, President of Belarus, since 20 July 1994
• Albert II, King of the Belgians, since 9 August 1993
• Harald V, King of Norway, since 17 January 1991
• Hans-Adam II, Prince of Liechtenstein, since 13 November 1989 (he has already handed over most of his powers to his son)
• Beatrix, Queen of the Netherlands, since 30 April 1980
• Juan Carlos, King of Spain, since 22 November 1975
• Carl XVI Gustaf, King of Sweden, since 15 September 1973
• Margarethe II, Queen of Denmark, since 14 January 1972
• Elizabeth II, Queen of the United Kingdom (and therefore ruler of various other bits), since 6 February 1952

Noticeable that while women are under-represented as a whole, they are less so in the list of long-lasting heads of state where they are three of the top five (and Tarja Halonen of Finland just missed my cut, as she was first elected in 2000). However the only woman currently serving as head of government in Europe is Angela Merkel in Germany. (Again, one might have to also count Micheline Calmy-Rey, of the Swiss Federal Council, who will probably be President of Switzerland next year.)

The longest-ruling monarch in the world at the moment is Bhumibol Adulyadej / ภูมิพลอดุลยเดช of Thailand, who has ruled since 9 June 1946.
The longest-ruling non-monarch is Fidel Castro, who became prime minister of Cuba on 1 January 1959 and president on 3 December 1976 (the post of prime minister was abolished at that time; the president is head of government).
The longest-ruling non-monarch who hasn't changed job title since he came to power is Omar Bongo Ondimba, President of Gabon since 28 November 1967. He hasn't changed job title, but did change his own name to Omar from Albert-Bernard when he converted to Islam in 1973 and added the Ondimba part of his name in 2003.
The longest-ruling non-monarch who has changed neither job title nor his own name since he gained power is Muammar al-Gaddafi / معمر القذافي‎, of Libya. However this is a bit of a stretch because he doesn't actually hold any formal office in the Libyan state.
The longest-ruling non-monarch who has been formally in power without changing either his job title or his name for longer than anyone else is Maumoon Abdul Gayoom / މައުމޫނު އަބްދުލް ގައްޔޫމް, President of the Maldives since 11 November 11 1978.

Gosh, I'm glad I worked that out.