Fine tuning details in C++ function for different customers

The company I work for follows a business model where a core product exists (originally written in C, now in C++) with some default implementation but details are tailor-made for each customer (there are cca. 10-20 of them). What’s the best programming approach in such a scenario? Is there a good design pattern/methodology/paradigm/whatever out there that makes code reuse and maintenance optimal? (Versioning is just as much a headache, maybe it will be another SO question later).

Example: the system provides a service implemented as a function:

int doServiceA(const string & params);

A common dispatcher routine calls this function:

void dispatch(const string & cmd, const string & params)
{
    int ret = 0;
    if (cmd == "serviceA") {
        ret = doServiceA(params);
    }
    //...
}

In our earliest approach the implementation of doServiceA was littered with #ifdef’s to handle customers’ unique requirements.

After a couple of years we switched to using virtual functions:

Core module:

class ServiceA
{
    virtual int execute(const string & params); // with default implementation
};

ServiceA & getServiceA(); // factory method declaration

void dispatch(const string & cmd, const string & params)
{
    int ret = 0;
    if (cmd == "serviceA") {
        ret = getServiceA().execute(params);
    }
    //...
}

Extension for customer XXX:

class XXXServiceA : public ServiceA
{
    virtual int execute(const string & params); // implementation containing XXX-specific parts
};

ServiceA & getServiceA() // factory method implementation
{
    static XXXServiceA s;
    return s;
}

Extension for customer YYY:

class YYYServiceA : public ServiceA
{
    virtual int execute(const string & params); // implementation containing YYY-specific parts
};

ServiceA & getServiceA() // factory method implementation
{
    static YYYServiceA s;
    return s;
}

So far we’ve been OK with this technique, but I have some concerns:

1. How do I differentiate from the default implementation when a customer requests a tiny change in the middle of my service? I guess I should break up ServiceA::execute() to pieces as small as possible and make them all virtual (as I really can’t foresee which parts are going to be customized later)?

2. Creating an object with no state feels like I’m violating the concept of OOP for techincal reasons.

3. Sometimes a change makes sense for multiple customers which results in either code duplication (XXXServiceA and YYYServiceA with partially same implementations) or complex inheritance hierarchies (when adding a class between ServiceA and its descendants to accommodate common code).

4. Just a feeling that virtuals may not be the right tool here as it’s a means to achieve runtime polymorphism whereas what I need is compile-time polymorphism (no XXXServiceA and YYYServiceA objects will exist in the same binary).

I experimented with a lot of things I read about (policies, mixins, CRTP) but so far I failed to improve much on the above design. I am wondering if I am missing something really simple here?