I've got the same setup (04 euro + iphone4) and just bought a Dice unit for my car, and very happy with it. Cost me about $170 landed from ebay. It allows you to flick through songs with your steering wheel buttons and headunit, or by controlling it directly on the iphone at the same time. You don't have to muck around with playlists or anything. The unit has further navigation capabilities if connected to later model headunits that support text etc, but in the 04 euro it's a bit more limited. Never tried the x carlink, but would recommend the Dice unit from my recent experiences.

Ollie