Reinhard Müller notes an instance of the use of a down-under deal in “Das Ablegen” (“The Discard” or “Putting Down Cards”) from R. P.'s Ein Spiel Karten, 1853, p. 68 in the Pieper translation. The challenge was to arrange the thirteen spades in such an order that when the first card is dealt face up it is the Ace. The next card is ducked, the third card dealt (the Two), etc., until all the cards are turned up in Ace to King order.
The earliest mention of the down-under deal listed by Jack Potter appears in A. Anderson's How to Do Sixty Tricks with Cards, 1900, p. 33, as “The Alternate Card Trick.”
In The Phoenix, No. 98, Jan. 4, 1945, p. 397, Rusduck published a trick in which cards were dealt alternately face up and face down, and the face-up cards were eliminated. John P. Hamilton, in The Phoenix, No. 140, Dec. 12, 1947, p. 562, built on Rusduck's elimination procedure. In Pallbearers Review, Vol. 5 No. 10, Aug. 1970, p. 354, Karl Fulves states that Hamilton named “a development of the deal…the Australian deal.”
Such uniform arithmetic patterns for elimination are very old; e.g., the ancient Roman practice of decimation.