I did end up writing a C program to do the path fixing; it makes a big difference when the system is under load.

fix path in c

Then I have to change my bashrc a little bit from before:

PS1="${PS1}$(fix_path)"

And now it's all spiffy fast.

UPDATE 2009-07-20: The line above actually has an untrusted code excecution vulnerability. If the user can be tricked into navigating to a directory with something like $(foo) or `foo` in the name, then the foo program will be excecuted. This is quite bad. The problem is that the shell evaluates the PS1 variable before display. So we need to change that line to:

PS1="${PS1}\$(fix_path)"

And we postpone evaluation to when the prompt is displayed, instead of evaluating it both when PS1 is set and then again when it is displayed.