Better accuracy requires more time, more time doesn't guarantee better accuracy, and there's no getting around it. In my experience, though, the 95% confidence radius ("accuracy") leans towards being pessimistically large. How are you resolving coordinates to addresses? Geocoding and reverse geocoding as implemented by common web services can be very inexact. There's a lot of interpolation that may not exactly match the geography of actual properties. Can you describe more details of the application you're building? Some approaches I can think of may or may not apply to exactly what you're trying to do. When I have a database of possible addresses a location could be, I use the coordinates to show the user a shortlist of possibilities, and the user always has to pick the actual address.
If you're reverse geocoding with a web service, you might try sending several queries with coordinates randomly "jittered" within your confidence radius to get a list of possible addresses for the user to choose from. If none of those is exactly right, you might let the user pick the closest match to modify for use. I haven't tried this, though; it's just an idea.