And if you have to rebuild your database, or lose those .picasa.ini's, guess what, everything you ever starred is gone!
How to prevent this: unfortunately, I've found no automatic way, but here's a quick manual fix:
Select all of your starred photos (easy to do by selecting the starred album in Picasa) and then add to all of those photos a tag called "starred". (Tags are stored in the metadata in the picture file itself.)
After doing so, you can easily find starred photos, no matter what may happen. But unfortunately, everytime you star or unstar something, you'll also have to add/remove the "starred" tag.