Why does the FIDE ID change sometimes? I noticed that FIDE ID (unique ID used on FIDE rating lists) changes for some players. E.g. Igor Khenkin had 3 different IDs (4659600, 4135814 and 2802350).

Sometimes (like for Khenkin) ID changes when player switches federations, but most players change federation and their FIDE ID stays the same.
Also, some players (e.g. Yimam Abera) have their ID changed while everything else stays unchanged.

Worse, it seems old ID can be used by different player (e.g. Shirov's 11600012 was later reused by Olegs Marutkins).

Are there any rules here? Is there a way to decide which FIDE IDs belong to the same person?
Actually it is worse than you say. Igor Khenkin has had a total of 5 FINs (FIDE ID numbers)! He has had the following FINs -

62480 (January 1990, FINs first introduced)

4101430 (July 1990, oops! What happens if we have more than 99,999 FIDE rated players? Make FINs longer. Everybody's FIN changes)

2802350 (July 1993, Khenkin changes federation from RUS to ISR)

4135814 (January 1998, Khenkin changes back from ISR to RUS. Note he doesn't get his old number back)

4659600 (January 1999, still not happy he changes federation from RUS to GER)

Note also that the situation with Shirov's FIN - 11600012 - is also worse than you suggest!

In the January 1990 list when FINs were first introduced the player S. S. Alsharfi from South Yemen was given 71366. Six month later when the longer FINs were introduced his FIN was changed to 11600012. By the time of the January 1991 list South Yemen and North Yemen had merged into Yemen. This meant a new federation and so his FIN was changed again to 9400010 leaving 11600012 free.

Meanwhile Alexei Shirov's FIN history looks like this -

82074 (January 1990 list - short FINs, he is playing for USSR)

4100220 (July 1990 - long FINs)

11600012 (January 1992, FIDE recognizes the breakup of the USSR and Shirov becomes a Latvian player, with a new FIN. Except it is actually an old FIN previously held by the South Yemeni player)

2209390 (January 1995, Shirov moves from Latvia to Spain and gets a new FIN leaving 11600012 "vacant" for use by a Latvian player)

In October 2008 Latvian player Olegs Marutkins gets Shirov's old number.

The current FIDE rating website goes back to 2001 and doesn't seem to have knowledge of FIDE ratings and FIDE rated players before then. Players who were inactive then and who have remained inactive do not appear. One example would be the current British chess problem solving champion, English player Ian Robert Watson. He was active from January 1978 through January 1984 with a rating varying between 2200 and 2215. He played before the era of FINs and doesn't appear in FIDE's records. He still plays local club chess and has an ECF rating of 198 which is roughly equivalent to 2200.

However since 2001 the FIN changes with federation seem to have stopped. For instance Fabiano Caruana had the FIN 2020009 in 2004 when he played for the USA. When he changed federation in 2005 to Italy he retained the same FIN and again when he changed back to USA in 2015.

OlimpBase is a good source of information. The FIDE rating website only has information from 2001 while OlimpBase has records going all the way back to 1967 when unofficial rating lists were first produced.

FIDE first gave out FINs in January 1990 but they were only 5 digits long. Somebody worked out that this didn't give much room for expansion and so when the new list came out 6 months later everybody got a new, much longer FIN.

Note that OlimpBase has collected this early rating information which can be downloaded here. They also have information for the period 2002 through 2009 here. This was what I used as the source for the information above.