I'm guessing then that one doesn't exist and I should be signing up for multiple providers to cover them all?
You're guessing wrong - such companies do exist, and have done since at least the mid-1990s. The problem is that most of them are quite expensive because they target multinational companies rather than small business or private individuals. Large companies will generally just go to ONE provider with instructions to "register my name in every TLD under the sun".
Companies like Markmonitor, Ascio and Com Laude will almost definitely be able to help here - but at a price.
I've looked at some others - i.e., ones that are more geared up to retail customers - and it would seem that com.au is a bit of a stumbling block (is it a restricted TLD?). However, I've found one that offers all three of the ones mentioned by the OP (as well as everything else), and that's BB Online here in the UK (www.bb-online.co.uk)