The decision to choose a "mail client" (really a "groupware system") is a complex process in most cases. MS Office is the default because it does everything, and it works on the top two platforms. Google is sort of competing in this space, but it's nowhere near MS's feature set, customer/business service, and compatibility.
The people buying your product are not integrating it into their business case because your product can't compete, it can only fill a niche. In this sense you should definitely find niches, such as users willing to pay money to have a working client on Linux. But this can be a dangerous game. If, for example, Evolution suddenly stopped sucking balls at Exchange compatibility and became a half-decent mail client, you could lose your niche, and your cash flow.
If I were you, I would make your product be as different as it can be while still being compatible. One way would be tightly integrating with an OS or product. Another way would be providing custom integration that competitors don't even come close to. Another would be to provide utility functions that nobody else has. Getting to the point where people use your product not because they like it, but because they have to have it. Kind of like the iPhone. Nobody ever needed a giant glass touch screen, but once people started using it, they couldn't give it up.
Once you have that kind of core functionality, you could give away a stripped down product and ask for payment for premium features. This would net you additional users that would otherwise go to a free competitor, and be a potential entry to sales once they feel they need the extra features.
(apologies if you're already doing any/all of this)