But, in a time crunch, I found a service that would remotely unlock the phone, such that it was entered into the databases of Apple and AT&T as such. How does that work? I'm not sure. My guess is that this UK-based unlocker is registered as an authorized buyer and seller of iPhones, and therefore have access to that kind of proving channel. In any case, I paid a small fee (they usually range from $5-$35), and literally 2 hours and 15 minutes later, I got an email notifying me that the phone was ready to roll. I plugged the iPhone 5 into iTunes, and it said:
Congratulations, your phone has been unlocked.
Not very excitable, that Apple. In any case, after the APN change and an unlocking, the iPhone and Straight Talk were finally talking. Learning why things weren't working took some time, but actually solving them was filling out a form and waiting a few hours. Overally, it was worth the long-term savings.
What did we learn? To always buy an unlocked phone when trying the no-contract waters. And that phone unlocking is, like most personal tech matters, not something the government is exactly great at crushing.