I originally held off answering this question, but I feel I have to share my opinion, even though it may not be the most popular. For a start though, it irks me a little that you have come to Server Fault after an "answer" and subsequently reveal you are not an admin and presumably can't even make this change happen. It also winds me up a little bit that your question and subsequent comments seem to be a big whinge about your admins. I think your only saving grace is that this question may be valuable to others on the internet searching for such a solution. By all means direct your admins here for some sensible discussion and we'd certainly welcome it and try and give them some good advice.
I sympathise with your predicament of ridiculously small mailboxes, I really do, however I don't for a second believe your admins are being draconian about it for no good reason. It is often the case that money simply won't allow it and you just have to work with what little you've got. Unfortunately it may take a very bad situation such as someone deleting a very important email because their mailbox was full before management realise the extent of the problem. In the mean time your admins will be forced to enable mailbox quotas, because if they don't and the disk totally fills up they are going to have a much bigger problem and email will be down for everyone.
Single instance storage (SIS) is not the magical solution you think it will be. SIS will certainly slow down the rate at which disk space is consumed, but I can almost guarantee not to the level you think it will. In actual fact, Microsoft have long recommended you totally ignore the disk space savings you can achieve with SIS when sizing mailbox servers, because there are quite a few ways to totally blow some of your SIS away. The only real solution is adding more mailbox servers with more capacity, but again this is very much constrained by budgetary limits.
I understand you're on Exchange 2007 but I'm going off on a little tangent here to give you some more info on SIS. One of the reasons the IO requirements in Exchange 2010 decreased was by removing SIS. That among other reasons means Microsoft now think it's acceptable to use slower disks (which will be cheaper) without seeing a massive performance hit. I'm in the UK so I can't comment on your situation, but certainly over here enterprise grade disks aren't massively expensive. The bottom line being that SIS incurs a performance penalty, and to get around that you might be forced into buying more/quicker disks to offset this.
As for a total mail sever migration, that is definitely not something to be taken lightly and I'd go as far as not recommending that, and I'm a guy who'll recommend what's right for the job, not what will make me most money. Heck, even Exchange upgrades need to be carefully thought out so they go as smooth as possible with as little downtime as is practical. You've made a significant investment in Microsoft Exchange, and I dare say user productivity will take a hit (even if only in the short term while users get used to the new system) and there will be complaints that
$NewMailServer doesn't do all the shiny things Exchange did.
If you did go for a total mail server migration, there is an awful lot of cost involved in that too. You've got admin training on how to manage the thing, user training because things will work differently, then you've got the actual migration to do. The migration itself may involve downtime, it may involve clunky imports (that might not SIS your mail and may actually undo any single instancing that Exchange 2007 has done) and a few other gotcha's you'll only find out about after encountering them.
You've also got to think about your admins. If they're all Windows people, and someone suggests you move them over to (for example) a Linux mail server they may well freak out. If I was told we were moving to a Linux based system and there was no option, I would actually leave. I am a Windows guy through and through and while I use Linux where I think it's appropriate, I don't particularly enjoy dealing with it or even want to if I'm perfectly honest.
Sorry for my wall of text, make what you will of it. Sorry for the little rant at the beginning, but I just felt that I needed to say it. Ultimately though, I'd say you need to sort out your underlying problem of lack of storage rather than trying to paper over the cracks. If your admins do have any questions, please get them to ask a question on Server Fault and we'll be more than happy to help.