The dongle did not come with my Force3D HD3850 either, but the supplied cd drivers included HDMI audio (no separate Realtek HDMI audio driver as with my HD2600XT installation) and the box was plastered with HDMI references (I use XP SP3).
I already have a HD2600XT with Black DVI to HDMI adapter (Rev A), this did not work with my HD3850.
You need the Rev B Grey adapter (6140063500G), I brought one from ebay, it actually arrived today, and works fine (I can only test stereo to my TV's HDMI input, but that's ok).
The ebay seller was in Greece, he only had a couple and has now sold out, and although the description made no mention of ATI p/n, the picture was Grey. I asked him to confirm p/n and it was 6140063500G. It was only £3.99 deilvered so I am glad I took a small risk.
There are others that turn up on ebay, so it is worth searching (US ones were a bit pricey).
This is the seller's shop, you may be able to request him to get some in for you.
http://stores.ebay.co.uk/gr-kiosk
The 4400/4600 series are about to be launched, if they use the grey rev B dongle (like the 4850), supply could improve. Hopefully their arrival in the market will prompt european shops to stock the adapter to feed the increased demand.
btw I managed to get MSI to give me the REV A adapter for my HD2600XT, as it was not included in the box. It was included in the reviews they referenced on their website, hence my emailed complaint had some weight.........it could be worth emailing the shop and graphics card distributer.