Carrier locking uses the IMEI number to white list and black list devices. Carrier locks are performed at all the cell towers and not in a specific device. Think of this like correcting your home address with several agencies that maintain shared databases of records, you're convincing them to change their records.
Start with the carrier that you want to pay for service - have them verify that your device is eligible for service. Since you are paying them, they should be able to explain exactly why they won't service your phone. If it was an error by TalkTalk - they have the capacity to request the other carrier fix the registration records on the shared database.
Apple lists carriers that perform unlocks at: https://support.apple.com/en-us/HT204039
You might choose a carrier based on their ability to help you with this problem or error. You might also need a copy of the original purchase if you believe Apple or the original retailer messed up the initial setup of the IMEI for your phone.