I've zoomed in on Sheffield and
1. Not all addresses are mapped
2. Not all the addresses that are mapped have postcodes
Adding postcodes to existing addresses I find is most easily done by using chillly's [chillly's postcode layer layer][1] in JOSM. Some guesswork is involved, especially where there is more than one postcode shown on a single side of a street, but with practice I suspect you'll get over 99% accuracy (with no figures to back this up).
For completely missing addresses you'll need to go and collect the house numbers first, then determine the postcodes in the same way as described above.
When you say you are getting the wrong postcode, if you are only using OSM data then whatever is giving you a postcode is probably returning the nearest one that is mapped to the co-ordinates you're specifying. [This Overpass query][1] query][2] shows how uneven the addr:postcode tag usage is in the area.
[1]: https://wiki.openstreetmap.org/wiki/Ordnance_Survey_OpenData#CodePoint_Tiles
[2]: http://overpass-turbo.eu/s/Zrj