You should look into archiving first, if you havent already. Any good archiving solution, with a basic set of policies of emails over 90 days and attachments over 3MB, will reduce most mail stores in all the companies I've supported, by more than 70%.
Shrink the mail store by 70%, and who cares what the dedupe ratio will be...
But there are a number of NBU 7 patches coming down the pipeline to improve it's performance.. In late May there is a significant one to look forward to.