I can't remember which chain it was but I'm sure I've seen stats on in-progress rollouts of protocol changes where the network took something like weeks or months to all get upgraded to the new version. You can design for tolerating both for a time.
Yes - definitely not impossible, just something which requires coordinated deployment as opposed something the two parties to a connection can do themselves.
