I don't have a solution to your problem, but maybe some more ideas what you can try. I understand that you actually want a solution which would allow you to import the large excel file directly without workarounds, but as you have seen that might not be possible. You might want to contact WRI in the hope they will improve the import in future versions. For now here are some things I would try, but honestly I doubt they will solve your problem:
Import only parts of the file at a time, which would be possible with something like:
col1 = Import["testfile.xlsx"], {"Data",1, All, 1}]. Actually I think there are chances that this could help for xlsx format if the data is distributed over several worksheets, since it could well be that these are read as single entities. In all other cases I wouldn't be surprised if all the data is read to memory but only what you ask for is transfered to Mathematica -- which most probably wouldn't solve your problem.
use the COM interface to get access to the data, depending on you knowledge of Excel this might or might not be difficult to do. See the section "Calling COM from Mathematica" in "NETLink/tutorial/Overview" for a simple example to get started. I wouldn't expect this to be very fast though, but if you actually only need part of the data it could be worth a try.
If you look at how import of excel files is implemented in newer versions of Mathematica you will find evidence that it uses a java library (jxl.jar) which can be found in the Converters/Java directory of your Mathematica installation, maybe you can find information on limitations of this library. The error message you see looks like a general message issued when the underlying java routines throw an exception. For your large file it might well be an exception due to memory problems, but it could just as well be something else. If it really is a memory problem increasing the java heap size would actually make sense, but probably you just can't make it large enough. Have you tried a file that is somewhat smaller, but still will give the same error with the standard settings and then checked whether increasing the heap size would help?
Just a side note (because you mentioned difficulties to explain this limitation of Mathematica): I just had a similiar problem in matlab when importing huge (well, about 30-50MB uncompressed) xml files: there the resulting exception caused a crash, so the unhelpful error message of Mathematica doesn't compare that bad. While increasing the heap size did help there it didn't solve our problems completely (there is not much room for correction if a wrong guess causes a crash, end there were some additional problems with character encodings). We ended up to parse the xml-file as text, which wasn't that difficult. The final code is very fast and reliable and we have full control over memory usage that way. If you are after a practial solution I guess you'll end up doing something similar in your case...
Importboth run-time and memory-wise, and actually made it possible to import the file. Of course, I was relying on CSV format specifics, so this may not work for your case directly. – Leonid Shifrin Apr 2 '12 at 18:01