Well, I've discovered the algorithm used to generate the PID and was able to use it on Fictionwise, but there was another catch. AZW files have a flag set in the DRM info which is not present in books bought from other vendors. After fixing that, I could read the book on Kindle.
Linked archive includes two Python scripts.
kindlepid.py generates Mobi PID from Kindle serial number. You can then add this PID at a Mobipocket vendor site and redownload books with Kindle's PID enabled. It's possible that some vendors will refuse this PID, as it has an asterisk in place of the traditional dollar sign (Fictionwise works fine).
kindlefix.py "fixes" a Mobi book so that it can be read on Kindle. It should already include Kindle's PID (which you need to specify too). The script will output the fixed book with .azw extension.
Kindle Mobipocket tools