Apparently there are are many revisions of the RNS-E head unit and the corresponding bluetooth module (e.g. for the RNS-E head unit, I have version 74). There is also a MY 2010 version which looks the same, but is technically very different (higher resolution display, faster CPU etc). I queried audi.de and it looks like the required functionality is only available on the A4/S4/RS4 for units after 06/2009 (which is probably the MY 2010 unit). Same is probably true for the A3/S3, TT and R8 (which all use the RNS-E).

I guess I have to replace the head unit if I want to get this fixed for any Nokia phone that is not able to run the 810 Contact Downloader. Give the fact that this is more expensive (cost approx EUR 1500) than any decent smartphone on the market, it is not the most attractive option.

Seems silly that the AT commands are not supported, but if this is the way it will be with all new phones I will probably reconsider.