I've done the following. First, I created an intercepting filter, to intercept all web requests, I also created a version which would work with command line commands.
Both interceptors would go to a boot strap file, which would setup an autoloader. This file as the autoloading function and a hash. For the hash the key is the class name, and the value is the file path to the class file. The autoload function will simply take the class name and run a require on the file.
A few performance tips if you need them, use single quotes in defining the file, as they're slightly faster since they're not interpreted, also use require/include, instead of their _once versions, this is guaranteed to run once, and the former is a fair bit faster.
The above is great, in fact, even with a large code base with a tonne of classes, the hash isn't that big and performance has never been a concern. And more importantly we're not married to some crazy pseudo name space class naming convention, see below.
The other option is delimited name, pseudo name space trick. This is less attractive as name spaces will come with 5.3 and I see this being gross as renaming these across the code base will be less fun. Regardless, this is how it works, assume a root for all your code. Then All classes are named based on the directory traversal required to get there, delimited by a character, such as '_', and then the class name itself, the file will be named after the class, however. This way the location of the class is encoding in the name, and the auto loader can use that. The problem with this method besides really_long_crazy_class_names_MyClass, is that there is a fair bit of processing on each call, but that might be premature optimisation, and again name spaces are coming.
eg.
/code root
ClassA ClassA.php
/subfolder
subFolder_ClassB ClassB.php