Does this affect the security of OTP?
Yes, it destroys the notion of a OTP and your system reverts to an algorithmic cipher with it's strength equivalent to the strength of the scrambling method. This becomes a permutation of the OPT, so mathematically this is noticeable due to non repetition of characters. It's difficult to compute as the plain text can change, but 10! combinations is < 4 million. Say root that to ~1900 and I'd be uncomfortable sending more than that if every message is different.
When is the first message vulnerable to decryption by an adversary?
Imagine @fgrieu's suggestion of a plain text leak. The first one. And then the next message is the same plain text, say "No change." And the larger contextual/semantic environment hasn't changed. The probability that the same message was resent must be >> 0 as all the letters are there (albeit translated). A modern adversary will not only use maths, but sociology and psychology as well.
I can't do the maths, but the certainty will quickly pile up if you keep sending "No change." There might even be a formula for this. A simple way to view it is to drop the initial OTP bit as the transpositions become fixed. All you have remaining for security is permutation (under some RNG seed?) And we don't do that.
I think that you have a sense of the answer by referring to frequency analysis yourself.
Do all further keys (if none get leaked) still provide perfect secrecy?
It follows that if the system is no longer a true OTP, perfect secrecy cannot possibly exist.
We assume that Bob always receives the new (scrambled) key over a secure channel and no one else (ever) knows the key.
Isn't this the issue with OTP systems? If this channel exists, then pure OTP is the solution rather than this derivation. As a small note, there is also the issue of message integrity to consider which seems absent from the proposed scheme - the usual OTP caveats.