Wow, sounds like your insurance company sucks. With mine, i'd just call my broker and they'd do the legwork, including tracking down and obtaining the payment from the other party's insurance company. That's what I'm paying them for after all.

I'm surprised your insurance company won't seek the damages directly from the other company without you first having to pay a deductible - which you're obviously not liable for considering you weren't at fault.

I've only ever had this type of experience with my own car, not a rental, so perhaps your insurance company is only unwilling to go the extra mile in this particular case.