You need to search for Rochester, Medway, England.
This is of course wrong according to postal addresses, wrong according to most people’s intuition and expectation, but correct according to administrative boundaries. How exactly are you searching?
I’m searching by typing “Rochester, Kent, England” in the search box of the top left hand corner of http://www.openstreetmap.org/#map=12/50.2367/-119.3900&layers=N
Perhaps it would be possible to allow both search strings to find Rochester? I don’t believe people search by “administrative boundaries”, they search by what they know, which in this case is that Rochester is in Kent.
The software behind the search box is called “Nominatim” and it’s maintained at https://github.com/twain47/nominatim .
If you create an issue there the maintainers will have a look at at (actually, I’d check that someone hasn’t already created an issue like this). The relevant relations here are http://www.openstreetmap.org/relation/172385 (the boundary of the administrative county of Kent) and http://www.openstreetmap.org/relation/88071 (the boundary of the ceremonial county of Kent).
I added is_in=Kent to Rochester (and Chatham and Gillingham) and now the search works as expected.