The fact that you're from Australia will limit the amount of prospective buyer's from this board, there just aren't alot of peeps from your part of the world kicking it here. I'm assuming most of what you own is PAL. And common games, and starter packages aren't as easy to move on a board where most everyone already has that sort of stuff anyway.
Even thou ebay can be a pain, it's still the most widely used of all the auction sites, and you'd run into the same issues on ANY online auction site, only difference, is you'll see fewer bids elsewhere. IF it gets any bids at all.
Yahoo is the next best thing to ebay, then you have Bidville & Epier, I'm not sure what else is still around. There are some geared towards electronics and whatnot, but still ebay is the best.
And as far as Paypal goes, that's the most convenient of the payment services around, and is probably the best option for you as a seller. Fees do suck, I believe even living in the US, my fees go up when I accept Payments from overseas. It's been awhile since I looked it up, but I think it's an extra 1% or .30 cents + 3.9% of transaction. You could probably adjust your "handling" charges to offset the costs of payment services?

I know most people, including myself are against such actions, but still you have to do what's best for you.
Ultimately, you would best off selling stuff thru ebay, and accepting Paypal. But it doesn't hurt to at least try to make some sells/trades here first.
And I agree with everyone else's statements, This is the BEST board to work out deals with other collectors. It's rare when someone does come in here and tries to cheat/lie/steal from other members. That sort of stuff happens daily on some sites.