BUT.... I think this would be a great opportunity for someone to bring this type of service to market. A service that is hassle free, you put one currency in one end and you get another currency out at the other without the user doing much at all.
I think the problem you face here is that you are simply trying to change currencies twice.
Going from AUD -> EUR will have a certain fee.
Going from AUD -> BTC will have a certain comparative fee, and then you have to pay another fee to go from BTC -> EUR.
It's a bit like getting EUR by going: AUD -> USD -> EUR. There's really not much point in going via USD unless there are loads more people trading USD than there are people with EUR that want AUD (arbitrage/liquidity etc). The same applies to BTC, except BTC is a waaaaaaaaaaay smaller market.
BTC's advantage is if you were paid by your clients in Australia in BTC, and you could spend your BTC in Germany for whatever you wanted, within the hour. That's where transaction fees become nominal. The same could be done if you were paid in USD and paid via USD in Germany too, of course, but as we know the banks don't work this way, so BTC is a viable world currency option (no central bank creating them at leisure).