One thing that hasn't been mentioned yet but should be . . .
Check the trem posts on the body. This is often an underlooked component to Floyd tuning stability. If you take the Floyd off the guitar and can wiggle the posts, then think of how that variance translates to a strung up tremolo. A lot of licensed Floyd Rose units come with coarse threaded posts that end up having a lot of play when screwed into the studs. Higher quality Floyds typically come with fine threaded posts - which make a much more snug fit and allow more precise height adjustments.
Also, check the knife edges on the tremolo. If they are worn down or have flat spots then that will affect tuning stability. Usually this is caused by making height adjustments on the body with the Floyd still strung up.