The Flex SDK team finally decided to fix the problem with Adobe Air Auto-Update in Flex SDK version 3.5a. Here are the notes from QA on the bug:
The Flex team has updated the 3.5 SDK with a small update that addresses this issue. The refreshed build, SDK 3.5a, has only a few files modified in order to fix this issue and this change does not affect the signing and caching of the SDK 3.5 RSLs originally released in December.
We encourage all developers using SDK 3.5 to upgrade their build to SDK 3.5a to continue their development. The SDK 3.5a build can be found in the “Latest Milestone Release Build” table here: http://opensource.adobe.com/wiki/display/flexsdk/Download+Flex+3