This problem has been discussed in the mandrakeclub forum, with input from the wise man bgmilne: http://forum.mandrakeclub.com/viewtopic.php?t=31082
The executive summary is (as you have concluded) that hsfconfig doesn't know that Mandrake 10.1 uses udev, and therefore the configuration disappears after reboot. Kernel modules and everything else are still installed and loaded and should work, the only
problem is that /dev/modem (and /dev/ttyWhatever) has disappeared.
The official solution is, that you should be able to use DrakConnect and it should do the right thing where hsfconfig fails. But hey, when have the tools in Mandrake Control Center ever done anything right? Once again, there is some bug somewhere and it's just not worth bothering.
The real problem is, that with udev you should create a file in /etc/udev/rules.d/ that makes the /dev/modem permanent. I tried this with the information from the Mandrakeclub thread, and I think the modem might have been working, but X broke for me, so I had to remove the file.
A working solution:
The thing is, after you have run hfsconfig the first time, it remembers your answers and the next time you just need to answer one 'y' and press alot of enters. So it is not really that big a deal to rerun hsfconfig every time you need the modem. In fact this is easy to automate with a script and you can even call kppp at the end of the script so it becomes very convenient.
Here are instructions to make the script I used to solve the problem, (you need to be root):
0) Run hsfconfig once and check that the modem works.
1) Create a file /usr/local/bin/startmodem with contents:
# Mdk 10.1 uses udev and linuxant configuration programs don't.
# The program hsfconfig works, but after reboot /dev/modem has disappeared.
# Using DrakConnect should configure the udev part correctly, but
# let's face it, have the Draktools ever worked like they should for you?
# So the easiest solution is to just rerun hsfconfig after each reboot.
# This script should take care of it. And it starts kppp for you as well.
kdesu "/usr/sbin/hsfconfig < /usr/local/lib/hsfenters.txt"
2) chmod a+x /usr/local/bin/startmodem
3) Create the file /usr/local/lib/hsfenters.txt with content:
(this is the letter 'y' followed with a lot of newlines)
4) Optionally use DrakMenu to add a menuentry to call the program "startmodem"
Now, when you want to connect to the internet, instead of using kppp (or whatever) you use startmodem. It needs the root password, but that's the only drawback. After it finishes you are in kppp and ready to dial. kppp is not run with root privileges.
Hope this helps someone, it was the working solution for me at least.
PS. Lesson learned: I prefer Open Source solutions, not for ideological reasons, but because those are the ones that seems to work.