Dry Ice is used, however rarely are the carts kept at a sufficiently acceptable temperature.
Perth and Darwin and Melbourne are well known to hardly ever have dry ice, and the melbourne caterers look at you like you are asking for their first born if you dare ask for more (thats if they bother to turn up at all).
Effectively, an aircraft could go BNE-CNS-MEL-PER-BME-PER-BNE and only get 'iced' in Brisbane (the ice is usually good for 2-3hours). Far fetched - not at all.
I was quite unpopular with the Development Managers when I would regularly 'write off' entire perishable stocks if we were not supplied with ice. (Record was 52 sandwiches/wraps on a BME return).
Was bound to happen eventually. Although the article says they removed the product from service? Um, no they didnt?