I may have stumbled across a workaround for this while trying to fix this issue for one of my customers. I found just about the same issue you were having.
Our build is using the new P8Z77-V Deluxe board with an Ivy Bridge processor, running Windows 7 64 Bit Home Premium. We experienced the same issue where the computer would start, and immediately revert to the default fan profile (possibly the one stored in BIOS?).
Fan Xpert IS in fact storing your preferences in a startup file, and is loading them when Windows starts according to your last used fan settings. Every time you change an option in the Fan Xpert, it updates the preference file. This preference file is in XML format and for us is stored in C:\Program Files (x86)\ASUS\AsusFanControlService\1.01.02\FanStore.xml
From my testing, it appears that your fan profile loads when Windows starts the AsusFanControlService.exe file. Everything seems to be running fine. Until the USER logs in. If you look in task manager, the service "C:\Program Files (x86)\ASUS\AI Suite II\AsRoutineController.exe -open" runs "On logon of any user", and seems to overwrite user preferences with either a default, or your motherboards settings, causing you to have to "reload" your fan profile.
In my testing, I found that as a workaround, disabling this task in "Task Scheduler" (Windows 7 x64), keeps the last used fan settings active. The only apparent downside so far is that the Asus AI icon does not go into the system tray on startup, however, you can still seemingly launch and use the AI suite from the start menu, and use all of its features as normal without losing your fan settings.
Let me know please if this information was helpful to you!
If anyone else comes across this information, and finds it useful, please feel free to repost it anywhere you wish. It would be nice to have some replies here, so I know that I helped someone out!