Can you elaborate on exactly what kind of pricing you've tried that doesn't work or what you would be open to? For example, did you consider 'tiered' pricing, whereby when you reach a certain number of users, e.g. 100, 1,000, or whatever, you charge a flat fee, until you hit the next tier. For all users under that number, the per user fee holds.

I think you could also have different tiers/levels of support/maint, so that if the enterprise customer is more demanding/expects more then they should be ok to pay more for that service. I have seen this work very well with many of my clients.

Jeremy