Been there, done that.
Wire brush + liberal doses of brake cleaner sprayed on the threads -> repeat until statisfaction. If the threads are OK anyway, there shouldn't be a big problem with the installation after that.
Blasting media residue + paint patches can be removed with a bit of dedication and care (and a good metal wire brush). I usually remove all paint inside the shell, if necessary and just put lithium grease coat on the naked areas to prevent corrosion.
Apart from these, some OEM dried threadlock fluid on the bottom bracket cups can also cause resistance when turning them into the shell with bare hands. Don't remove this OEM threadlock layer, just make sure the shell threads are nice & clean and you install them correctly.
I've learnt the hard way that bloody BBs must be installed with the utmost care and attention to detail, and this attitude always pays off, especially at places where labourers are decently paid anyway.