There's a path limitation in WSS so when you have a document library with versioning turned on, at some point previous versions of a document will vanish into the ethers of SharePoint. It only happens with past versions so your current version is fine no matter how long the path is. To test this out:
- Create a document library in a WSS site and enable versioning
- Start creating folders inside of folders inside of folders
- Upload a document and do a quick check out/check in to create 2 versions
- Select the version history for that document and view version 1 of the document
- You should get a HTTP 400 Error - Bad Request (if not, create some more folders in folders and try again)
I don't know specifically where the cutoff is but in testing (and from logic) my gut would say after 255 characters which is a typical limit (it's the PATH limit in Windows) and would make sense.
So basically the rule here is to try to stay away from a folder taxonomy to organize information. META data and custom views in document libraries is so powerful as you can have everything living in one "folder" but viewed by category (or whatever makes sense for your organization). It's a hard shift from the file centric way of thinking but you can seed the troops with some tools to get them started, spend some time training them and showing them how a slice through their data is much more informative than the "where did I put that file" approach they currently use. It's a tough sell and you'll get a lot of resistance as people are comfortable with a structured file system to do their organizing for them. In the end there are a lot of benefits to viewing your information with a slightly different twist and you'll avoid problems like the one I described above (although your mileage may vary).