Your example is a great example because the secretaries are clearly filling in the gaps, such as

1. How much can you spend on this trip? 2. Is first/business class necessary? 3. Is a layover acceptable if it's cheaper? 3a. Is it better to have a 4am flight nonstop or a 7am flight with a layover? 4. Are there preferred airlines? 5. Are there preferred hotel chains? What's the hotel budget? Do you want to pay extra for a nice view? 6. What kind of car should you rent? Is there equipment you'll be handling?

etc...

This is the kind of stuff that's easy(-ish) to communicate by presenting a list of options to a user through an actual interface. It sucks doing it through voice; think of the old phone systems where you had to go through droning "If you would like to rent an SUV, press 1. If you would like to rent a sedan, press 2. To speak to an operator, press 0."

So no, you never had a voice interface for booking flights; you had a human brain to whom you delegated, which is very different.