When doing any census work, I highly recommend having a good modern map of any area you plan to study extensively, learning what you can about the area as it is now, and trying to pin down when things changed.
It's much easier to see changes between the historical map and the modern one if you have one on the screen and one physical map, rather than having to switch back and forth between the two. A paper map is likely to cover a much larger area than a map you print out from Google, etc. which will help when looking for cross-streets and other nearby streets in the neighborhood. And if the enumerator's handwriting is wretched, the physical map can be a huge help in simply reading what the street name is.
With that knowledge as a baseline, it is easier to apply all the strategies above at once -- locating the district boundaries, looking for neighbors who are around a corner from the address you want, and so on. Using a combination of these techniques -- comparing the addresses of neighbors between 1871 and 1891 censuses, to look for address changes -- may work.
Some cities allow you to pull up tax information about properties by street address, which includes data about the buildings on site, so you can see if the actual building was standing at the time of the census you want.
I've also been alerted to address changes by using the web-based address checkers -- if an address comes up as 'undeliverable' then the street name may not be the same, the building may not be there any more (or it may be a multi-family dwelling and the address-checker wants a unit number).
If there is a large building in the neighborhood like a hospital, finding that in the census and on the modern map might give you an idea of how the street address may have changed.
If you run into this problem with a US address, try the One-Step Webpages at
http://www.stevemorse.org -- one of which lets you search for street name changes.
Good luck!
Jan