Also, you can declare member variables as mutable which allows you to modify it from a const function. An example legitimate application for this is acquiring a read lock on a mutex from a const function.
But the const function could still accept a non-const reference to a mutex, and still produce varying behavior in a threaded situation. In other words, what you're describing as the const contract sounds a lot like a pure function, which it definitely is not.
I'm not sure how it would produce varying behavior if it satisfies the const contract, in regards to the object itself.
You're passing in a non-const reference, so wherever that came from would be expected to change. However the object itself would not change. Your object would be at StateA regardless of who gets the mutex first.
You could also argue that read/write locks aren't legitimate applications (starvation, increased contention, alternate solutions).