ヤフーオークションでも私のクレジットカードは使えなかった...

まず日本の金融機関の多くは日本在住の人（住民票がある人）しか口座を新規開設することができないと思われます。
また、インターネットバンキングの利用開始時には暗証番号が書留等で届き、配達時に郵便局員が免許証等で本人確認をするケースが多いです。以前に開設した口座があっても、現に海外に住んでいる人がネットバンキングを利用しようとするとこちらの手続きがネックになりそうです。
海外への転居前にインターネットバンキングの利用登録を済ませていた場合、海外からのインターネットバンキングは自由に利用できるところが多いようです。
反対に、海外のIPアドレスからのインターネットバンキング利用をブロックする金融機関もあるようです。
このような対応には賛否両論あると思いますが、マネー・ローンダリングへの対応強化やハッキング対策を考えると仕方が無いところもあるかもしれません。（アメリカの金融機関のマネー・ローンダリング対策は非常に厳格に運用されていると聞きます。）
Yahooかんたん決済はマネー・ローンダリング対策を行う義務を課されていないと思いますので、自主的な努力で海外クレジットカードの利用を止めているのだと思います。

なお、Yahooオークションの規約上許可されているかどうかは確認していませんが、出品者への質問で「western unionで送ってもいいか？」と聞けばOKしてくれる人がいるかも知れません。最近、金券ショップ大手の大黒屋がwestern unionの窓口をしてくれるようになり、日本国内でも利便性が向上しました。ただしwestern unionの知名度がまだまだ低いという欠点があります。
http://www.e-daikoku.com/moneytransfer/store.html

paypalもまだ日本での知名度が高いとは言えませんが、日本の金融機関への出金が誰でも簡単にできるレベルになっています。ebayと違ってヤフオクの取引とは連動しないため面倒ですが、paypalは日本向けのネットビジネスに積極的に進出していくようですので近い将来にはヤフオクにも対応してくれるかもしれません。

私自身はebayでアメリカやオーストラリアから買い物をして良い思いをしたことがありますので、逆がやりづらいことは心苦しく思います。もし海外からの入札に出会ったら「paypal OK」と言ってあげたいと思いました。

yoheiさん、
丁寧なご説明ありがとうございます。
ご指摘のとおり私の場合、インターネットバンキングが始まるずーっと前から海外に住んでおり、日本国内の連絡先がないので、登録ができなかったのです。
Western Unionを知っているのは、少なくとも私の周りでは、多分昔インドに送金する時に使ったうちの旦那くらいでした。
PayPalが利用できるようになると便利ですよね。その日が待ち遠しいです。