First, how many cats are we talking about? I have read some airlines only allow 1 pet in F per flight, but I'm not sure if that was DL or another carrier. I know DL only allows one pet per person in the cabin.

It does seem to be standard practice for airlines to require pet payment on the day of the flight. I've heard various reasons for that, including they want to see how big the pet actually is, they want see if the pet is healthy, they want to count noses in the carrier and make sure you're not bringing onboard too many pets, and finally they want to make sure the pet actually arrives for the flight. Your guess is as good as mine as to what the real reason is.

But the Medallion line should at least be able to email or fax you some of confirmation of their reservation, even if it is only a screen print of however they log it in.