Here is a link to the exact limitations
http://technet.microsoft.com/en-us/library/ff919564.aspx
There is no way to really overcome these limitations. The limitations are there to make room for all of what sharepoint does with a url while keeping in mind the URL'S limitation which is not sharepoints fault.
Your only real option is to either rename all the files, or develop a custom Url Rewriter with a custom upload page on the files.
E.g. Modify your utility to build an Xml File of all the file names and give them short names, something like this
<FileNameRewrite>
<OldName>Really long name here.pdf</OldName>
<ShortName>P_0001.PDF</OldName>
</FileNameRewrite>
Upload the file as P_0001.PDF,
Then create an HttpModule that intercepts requests to either OldName or ShortName and retrieves P_0001.PDF (the short name) and design it in such a way that it catches link tags to, e.g. if someone creates a link to "Really long name here.pdf" it
loads P_0001.PDF.
To make this prettier, You could create a custom FieldType called LongFileMapFieldType and design it to be a hidden field.
Then create a document library in visual studio with a column on it based on the custom field type (Have it inherit from multi line text). Then modify the upload form on the document library to make the xml map and rename the file and save the xml in
the Custom Field type on the uploaded list item and the files bytes in the File.
Put the HttpModule in the same solution with an SPWebConfigModification to automate the whole process.
Then you can go to your custom document library and upload long name files to it, but only it.
Sounds involved, and is, but I can't think of any other way to do it unless you can get Asp.Net Url Rewriting to handle your problem.
-Edit
Was just thinking that users might want to rename P_0001.PDF to make more sense and in doing so would break the Url Rewriter. So you could go a step further and add Event Handlers to the List so that when the item is updated (e.g. it's Name Column)
you update the Xml Map so the HttpModule doesn't break.