What I don't get is how Apple didn't realize the IMEI or serial numbers were fake? Did they have some way of generating them so that Apple would see the device as under warranty.
None of those numbers are
printed on the back of the phone. Read the article. All the "phones" were ones that arrived non-operable. They just have to look convincingly like an iPhone in the
off state. It is possible (not easy, but possible) for someone to make an iPhone-shaped box (er, right rectangular prism with rounded corners, constructed of metal and glass and some ink) that looks convincingly like a real iPhone (keep in mind that
real iPhones also come out of a factory in China), especially if your (evil) motivation is, "if we build a very convincing non-functional replica for $50-$100 of materials and effort, we get a real replacement iPhone worth upwards of $600 in return" (and if you set up an assembly line to make the fakes, it probably costs you less than that).
Also keep in mind that the Apple employees accepting the returned "iPhones" are
expecting to see iPhones - they're not expecting to be handed a convincing fake. The customer doesn't start off by saying, "is this a real iPhone?" or "I assert that this is totally a real iPhone", they say, "my beloved iPhone won't turn on and my flight leaves in 90 minutes!" They frame the conversation around the points that it won't turn on and they're in a huge important hurry for other reasons.
And can you imagine how most customers would react if they brought in a legit dead iPhone and the Genius said, "hold on, we're going to have to take this in back and spend 20 minutes determining if it's a real iPhone or if you're committing fraud"? The customer would be outraged, their friends would be outraged, the media would be outraged (hundreds of repetitions "Apple accuses local upstanding citizen of fraud!" spilling into the national news), MacRumors forum denizens would be outraged. Apple's public image would take a hit.
It's taking advantage of Apple's policies that the customer is (almost) always right. Someone brings in their bricked "iPhone" and they're convincingly upset and need it replaced right away for <random made-up reason>, and Apple replaces it in a hurry (without being able to turn it on to check it out) because they want industry-leading customer satisfaction.