Ok, I discovered that this problem likely has to do with the version of the USB driver for the phone that Windows is using. When I set up AirDroid on Windows installed via Bootcamp on the same Mac to do a side-by-side comparison, AirDroid set up its own driver (Google Xiaomi) and (after resolving a naming problem, see below) it completed the negotiation successfully. However, the same steps done on the other Windows laptop (the one I aim for primary use with AirDroid), fail the negotiation. The difference as I see it, is that the driver provided for the USB link to the phone is by Microsoft (ADB driver) and no Google driver is getting installed in the process. I even tried to uninstall the Microsoft driver and install the one from Android SDK, but it doesn't seem to be picked up by the system and I don't know how to force it to use that driver instead. Any help with getting it to work would be greatly appreciated!
On a side note, during the negotiation on the Bootcamp Windows, a different error popped up, which indicated that the driver installer was trying to use my first name as part of the path (e.g. "C:\Users\First"), but my profile folder was named "C:\Users\First Last" instead. As a result, it failed to find something in that folder and that precluded installation. I then created a directory junction "C:\Users\First" pointing to "C:\Users\First Last", however a similar error occurred during the installation after that, this time trying to use the latter part of my profile folder ("Last\AppData\Local\..."). To avoid all of that, I had to create a different user with no spaces in the profile folder name and voila, it installed successfully and AirDroid started to work on that Windows system!
So it seems like the only remaining problem for me is somehow getting the Google driver to work on the previous PC. It would be great if AirDroid suggested to install the Google driver irrespective of whether the system already had some other driver for the USB connection. I suspect that currently it's trying to use adb command and succeeds, then it doesn't try to install the Google driver. However, somehow even though the Microsoft driver can be used successfully with adb, it fails the negotiation after that.