I realize that this isn't really an answer, more of what you probly already know & are dreading: seeing as how new systems don't come with compatibble OS's to your current version of software, an update to current OS's is certainly in order. Without knowing much more about the software [ you did mention a rewrite of sorts was to be avoided], I'm not sure what we really can do to help you out of this problem.
What about restricting the volume of data that you are willing to store for your clients? I'm sure this will be a VERY sensitive issue.
