1. I've "exposed" parts of the private implementation in that they were in the header file, yes. They were also labeled "private". That means that someone can read that and gain more information about my implementation then they could from just public information, I suppose. It also means that nobody can actually use them in code, because they're private. So you can think of that as "exposing" if you want, but it's not something that I've ever recognized as any kind of a problem, let alone one worth solving.
2. If you change only the private parts of the class and try to link other code to it without recompiling the other code, yes, you can get a broken compiled binary. That is certainly true. But I could do that in C almost as easily (if everything that uses the struct layout isn't in the same source file). And makefiles that keep track of dependencies aren't exactly rocket science. Neither are clean builds.
Maybe I just don't have your problems, but I'm still not seeing this as much of an issue at all.