Something very wrong is going on with IMEI blacklist. We had a brand new phone stop connecting to T-mobile's network (in the US). When we went in to the store

Something very wrong is going on with IMEI blacklist. We had a brand new phone stop connecting to T-mobile's network (in the US). When we went in to the store, they told us the IMEI was reported as a stolen phone. I brought back my receipt showing it was a new phone when I got it. They said they could not unblock because they didn't put the block in place, a carrier in Mexico did. The phone has never been used outside of the country, to the best of my knowledge. When I called the carrier in Mexico, they told me it was not possible for them to blacklist the IMEI of a device that's never been on their network, and that they had no record of my IMEI. I ended up returning my phone, at the expense of the manufacturer. Also, frequently when I sell my old phones on eBay, people love to ask for the IMEI to check the blacklist, but I believe they can also be programmitically swapped (the potential buyer has a blacklisted/stolen phone, and simply asks for a valid one), so I never provide it.