I'm not sure if CCleaner will be having anything to do with it being changed or removed. Have a look with "Start > Run > Type "regedit" (without the quotes), hit OK. Navigate to that registry address and see if you have an "order" entry inside the favourites folder.
My daughter uses IE7, and her favourites are pretty much all over the place, but they never change, even after using CCleaner.
If you haven't already, you could try organizing your favourites this way:
In IE, go to "Tools > Menu Bar (usually hidden) > Favourites > Organize Favourites, and arrange your links in the order you want in that window. Use left mouse button to drag each link to where you want it. There'll be an indicator saying "date modified", and that order should be reflected in the above registry key. It is on my pc.
That being the case, you could also "export" that key to a place/folder of your choice, to save in case you ever need to restore it.