What's their specific concern? (I mean besides from using a dedicated server from a company who thinks spamming is ok as long as they do it and no one else does.)
The number of files created by the database is a concern as most OSes max out at a set number of files per directory. (Usually 32k) You can code wpmu to use multiple databases and break them up.
wp.com uses code like this to break things down into 256 databases and one of the folks here have their own version of the code that does something simular although he hasn't desided on if they plan on releasing it or not and under what conditions. You may want to search the forums here for "multiple databases" as it's been discussed before. I'll let the person who wrote that code step up if they so choose.
I'd also sit on your "developers" as well. If you're paying them money and they're giving you vague answers like that, I'd be troubled. Developers, especially of open source projects, shouldn't be just stating flat out "no" when looking at an issue. They should be working on solutions to the issue as hand.
Either that or they should be over here looking for solutions instead of sending you to do it. That's why you pay them, right? ;)