Run linux process at very very low priority?

Have a look at cgroups, it should provide exactly what you need - CPU reservations (and more). I'd suggest reading controlling priority of applications using cgroups.

That said, put the important yet often idle processes into group with allocated 95% of CPU and your other applications into another one with allocated 5% - you'll get (almost) all of the power for your jobs when needed, while the constantly power hungry process will only get 5% at most at those times. When the computational surges disappear all CPU performance will be thrown at the remaining processes. As a benefit, if you create a special cgroup (with minimal performance requirements) for processes like sshd, you'll be able to log in no matter what is trying to get all CPU it can - some CPU time will be reserved for sshd.

If the process priority (nice value) is low then it will not be interrupting a higher priority process. The reason you're seeing the low priority process still consuming a significant amount of CPU when the higher priority process is running is because the higher priority process is not that busy. Probably waiting on IO. Use chrt -p -i 0 $PID to run the process at an even lower priority than nice 19 -p $PID (assuming we're talking about Linux here).

chrt -p -i 0 $PID puts the process into the "true" idle scheduler.

http://linux.die.net/man/1/chrt