'That being said, I don't understand why China either can't or won't verify degrees the way the rest of the world does with either a transcript or even a phone call.'
Don't use what happens at the provincial education department controlling a developed city like Shenzhen as the model for what happens elsewhere in China.
The problem you have is that you need a foreign experts'certificate in order to get a residence permit.The provincial education department head office staff in Shenzhen is ill-informed re Western degrees/diplomas,so the foreign experts'certificate won't be issued to you by said office at present.
The girl at your school knows about this because she's encountered you kind of difficulty before when applying for a foreign experts'certificate on behalf of a foreigner.And I'd expect it to be very hard to persuade the director of said office to change his view re unsealed transcripts.
But I would expect most other provinces in China to have better-informed provincial education department head office staffs.You can look for teaching vacancies elsewhere in China ,but don't delay,or else you'll limit your options.