It sounds like root cause is less the implementation of the software (or even the features in it) and more unthinking application of the default processes your software ships with. I would say you have two very different efforts that are being co-mingled - a software configuration process (resell, install, configure) and a business process re-engineering effort. I would suspect that many companies looking for BPM software are also looking for some process re-engineering.
You might consider trying to track and split the two separately, at least internally. One potential methodology that might help is to think of the two in terms of the Cynefin framework (here's a good description http://www.scrumsense.com/blog/cynefin-framework)
I see the two efforts like this:
A) Select, install, config the appropriate BPM SW - this is a complicated problem, and I would expect the one you already have decent processes for
Sense - get the initial requirements
Analyse - understand the appropriate config and customization based on what you know
Respond - figure out how actually implement
B) Work with the company to determine which processes they clearly wish to keep static and which have new (potentially implicit) requirements - this is a complex problem, and calls for a methodology more along the lines of a Scrum, Lean, or Kanban approach
Probe - quickly model the new / changing processes in a working instance
Sense - review (a la sprint review) with the client, get stakeholder feedback on what worked and what didn't
Respond - Amplify the positive signals (this worked, do more things like this, in the way you did them last sprint) and dampen the negative signals
If you can get clients to agree to model their contracts with you on this framework, so much the better; if not it is still an approach that allows you to clearly delineate where you can and cannot predict work and resourcing. At the very least you can have the conversation about your 'a colossal rate of failure when estimating time and other resources' in the context of a new framework, rather than in a witchhunt. Sounds very challenging - good luck!