Okay, a status update on my part.
Short story: Apple customer relations are fantastic, and they're replacing my 16gb iPhone 3G: 1.5 months out of warranty.
Long story: I called Apple reception and knowing that I'm out of warranty (as of early August) I ask for customer relations to apply for an exception to my warranty. I politely explained the situation. I live in a city (Adelaide, Australia) where there are no physical stores or technicians for Apple or my service provider (Virgin Mobile). I told them everything I've done to troubleshoot the problem; including multiple restores, restores without using my backup, DFU mode restores. I explained to them that I work in an Apple reseller, and deal with iPod service jobs and warranty claims like this all the time. They were satisfied that I'm an 'advanced user'.
The operator checked with a technician, then came back to me satisfied that i'd tried everything they would and gave me a green light on a replacement.
They're emailing me a post bag label so I can send them my iPhone, and they'll mail me back a refurbished unit.
Morale of the story: Call Apple. Be polite. Explain your situation.