Ok. I really need to stop replying to myself, but maybe this could be of help to someone else
Looks like both the 'intl' and 'idn' extensions need to be installed for php's idn translation functions. On my hosted 3.5 setup only 'intl.so' appears to be available, so still no go. As a workaround, I've found the 'Net_IDNA' library, available here:
Seems to be working -- at least the mail server stopped yelling at me...