Digging deeper into the issue I've found the following:
1) When the updated application is launched from the update installer it checks for updates. At that moment the updater is still in the memory and the updater process called from the application wrongfully returns 0 (which means updates are available). So the application starts waiting for the mutex, but it doesn't get signaled. The application receives the undocumented message 799, though.
2) The problem happens with WaitForSingleObject function also. It is even worse, as in that case you can't handle any messages. So I am pointing to the issues with the official guide:
http://www.advancedinstaller.com/user-g ... dater.html
3) It looks like the behavior is different on Windows XP and Windows 8. On XP the updater does NOT seem to return zero when the updated application is launched, so the program doesn't wait for the mutex and starts fine. On Windows 8 the updater for unknown reason returns zero, however, if I don't launch the application, so the update installer finishes and manually run the application after that it will check for updates correctly.