mod-rewrite: Locating a file in multiple directories
Use a programmatic RewriteMap:
RewriteMap rewriter prog:/path/to/script
RewriteRule ^(.*) %{rewriter:$1} [L]
And then in your script, take whatever part of the request path you want, iterate through your directories, and return the appropriate rewrite string.