Linux idea LAMP setup for search engine friendly urls

I worked on a site once where the apache server used some sort of traceback feature so if http://www.example.com/foo/bar/baz wasn't found, it would then look for http://www.example.com/foo/bar and if that wasn't found, it would look for http://www.example.com/foo

The cool thing was, I could easily have a file called foo and use .htaccess to make it parse as PHP, then foo could use the /bar/baz as input.

I know this can be done with mod_rewrite, but it would be much simpler to let apache's built in ability to do this for me. The only problem is when I try this on my servers here at work, and on the hosting server I pay for, it doesn't work. No matter how hard I try the only way to get this to work is to use a mod_rewrite, and to have it look more like http://www.example.com/foo.php/bar/baz (I don't want a file extension anywhere)

I will be setting up a LAMP sometime soon, and was wondering if there is a certain way I need to compile apache and PHP to make this possible.

It will be running on Novell's Open Enterprise Server (new enterprise version of SuSE 9.0) because we already have unlimited licenses for it ("free" updates and support!). I will be using PHP5 and MySQL 4.1, but am not sure what version of Apache to run (since it is supposedly bad to run Apache 2 and PHP5?)

Let me know what you guys think. I won't have the server until a few weeks from now, and I've allocated at least a week or two to install the software and run it through some testing before I need to work on other projects!