When Austrian told you to check with Lufthansa, what they meant was for you to check with Lufthansa if Lufthansa can transport your dog, not to check with Lufthansa if Austrian can transport your dog.
When I have to fly my dog, I always: 1. call Lufthansa Cargo to inquire about space for my dog, they tell me which flights have space and I ask them to “reserve” the space (they put it on hold for a few hours); 2. call Lufthansa to book the same flights for us (humans); 3. call back Lufthansa Cargo and give them the PNR of our flights so they can associate the space for my dog to the same booking (in that order). I too learned that the hard way but it is obvious that on any given plane the space for a crate is more scarce than the seats on that plane, so the space for your dog must be booked first.