I tried a lot in the past hours and it seems that the problem was not (only?) KRDC but rather (also?) related to KVPNC, NetworkManager and/or resolv.conf.
This is surprising given that KRDC recognized whether the server I wanted to connect to within the VPN exists, so the connection as well as the name resolution must have worked in some way. Maybe someone could give me a clue on what I could do to triage this further?
Anyway, I didn't change anything within KRDC. First I created /etc/vpnc.conf and added all the details. If this missing file caused a problem, there must be a bug within KVPNC.
Then I also edited /etc/resolv.conf and added the nameserver within the VPN as new nameserver and also added "search my.vpn.com" (where my.vpn.com is replaced by the acctual domain).
After all these changes, the connection worked.
A restart or new connection will, unfortunately, destroy the resolv.conf so it needs to be restored every time.
I'm using network-manager-gnome for connecting with my USB-modem (since knetworkmanager is currently busted), but connecting through ppp and the command line will require the same workaround. My VPN- connection is established through KVPNC.
In any case, the connection works "out of the box" under Hardy (install KVPNC, configure, connect through KRDC) and it also did so in the early stages of Intrepid. So there's definitely a bug. Is it resolv.conf? Is it the missing vpnc.conf? Or both?
Could anyone help me out how to triage this further? Are there any files worth attaching?