The flow you have described:
1- Set with PersistTo.Master (and check that it is successful)
2- Query with stale = false
should be enough.
This is what I do in Java and it works perfectly. (sorry I am not a .Net expert ... yet )
Keep in mind that observe is taking some resources to check the status of key.
So when you say that the PersistTo.Master does help, what is the status of the result?
If you want to wait, it is nearly impossible to say how much you have to wait, simply because it really depends of the cluster resources and activity on your cluster.
What is the exact use case when you need this? Testing? UI integration? (just curious)