> Неизменными интерфейсы будут только в том случае, если в интерфейсах используется не
> структура, а указатель на нее. В этом случае тому коду, который
> не лезет внутрь структуры, безразлично, что скрывается под void*, а тому,
> который лезет - ну, тут перекомпиляция при изменениях неизбежна.

Я правильно понимаю, что Вы предлагаете:
1) В заголовках писать только определение интерфейсов,
2) Описание структуры вынести из заголовков в код библиотеки,
3) Интерфейс-конструктор будет выделять память в куче и возвращать указатель на неё, а все остальные интерфейсы будут оперировать указателями структуры,
4) В программе, которая пользуется библиотекой, все переменные, подразумевающие хранение данной структуры, будут иметь тип void.

Если я правильно Вас понял и ничего не забыл, то в принципе это выглядит как решение... Но не станет ли код слишком громоздким?