30+ years ago I worked for a company in the UK which made float switches which contained magnets - when these needed airfreighting we had to pack the boxes in a special way on the pallet so that the magnetic fields from individual switches cancelled each other out, then go round the complete pallet with a gaussmeter to ensure that the residual magnetic flux at 1m from the load was within acceptable limits.
So you can airfreight magnets if you know what you are doing, but it's quite understandable why Carbatec won't (and why Australia Post won't accept them).