Windows DNS: dnscmd.exe with IDN zone names

I've automated some tasks for a client who is a web hoster.

One of these is automatically creating DNS entries in Windows DNS server.

Client has recently started to take IDN registrations (domain names with non-ascii characters).

On my virtual Windows 2003 Server machine, this command works:

dnscmd.exe /ZoneAdd oaké.be /Primary /file oaké.be.dns
DNS Server . created zone oaké.be:
Command completed successfully.

But on their server:

dnscmd.exe /ZoneAdd oaké.be /Primary /file oaké.be.dns
Command failed:  ERROR_INVALID_NAME     123 (0000007b)

I've checked "chcp" in the command line and set it to various codepages, to no avail.

I've also changed the regional settings in my virtual server to match the real one.

Name checking is set to "all names" on both servers:

Both DNS servers are the same version 5.2 3790

Has anyone had this problem and know what might be causing it?