Once money goes into an IRA, it's near impossible to get the IRA custodian to fix it without issuing a 1099-R. Unfortunately, it sounds like it is not their fault, but the broker's fault, and my experience with brokers is that you're going to have to tell them exactly and precisely how to fix this, and then cross your fingers that they don't screw it up again anyway.
I think - and it requires some more research and/or someone else confirming - that the participant needs to take it out as an excess contribution. That way the custodian is treating it as never deducted in the first place and not taxable when distributed. Although...I just re-read your message and I think it is too late for that now, sigh. I suppose you could consider whether treating it as a rollover gets the participant to the same place and whether you want to go along with that charade. It's probably the only practical solution at this point. I doubt you'll get the custodian to treat it as if it never happened.