MAybe you can check cheapassgamer.com for ideas. They have a trading forum there and have a ebay-ish feedback system. Maybe you can use that.

Wouldn't a simple reputation system (+1 for successful transaction, -1 for failed transaction) be enough for that?
As for the 'without loss' part, some trading places I've been involved in make it so that the giftee has to send out the money first before being gifted.

Ive also seen the one with lower feedback sends first. There could be also threads with a list of bad traders.

If they get banned for credit card fraud or the like not only will they loose their account but you will loose yours as well. So yeah... I'd not recommend getting random gifts unless you know the person very well. >_<

One way to try and deal with possible credit fraud is to avoid direct peer to peer payment. For an example, only accept Paypal payments to a master account. Person wanting a game submits a request through the site and provides say, the first 50% of the purchase price by default. (Higher rep accounts or whatever, could see that amount drop). Someone is then selected to provide the gift. Upon providing proof that they sent the gift, they get their payment in full from the site. The person wanting the gift then pays up the remainder once they receive their gift.
Yes, the gift receiver could still back out of the final portion of payment -- at which point the site takes a loss, and the gift receiver is black listed/banned from further participation.
However, there are still problems, especially with Steam. The person who sent the gift can still contact support and claim they sent it to the wrong account -- getting it removed from the account it was gifted too and getting their money refunded.
So the site would still need to be able to handle such cases. So perhaps you'll need a way to cut those losses to a minimum too. Perhaps by not allowing accounts to provide gifts for more than $9.99 until they have a proven track record.

Problem with that is that as soon as you're involving PayPal you are violating Steam's TOS by selling/trading gifts.
This whole thing needs to keep underground unfortunately due to (stupid) legal reasons.

No more so than by using credit cards or any other form of payment offered. For the record, I get all my US based gifting done via PayPal payments sent to the person gifting who then buys either via credit card or PayPal.
As far as the idea above goes, the person actually buying the gift can use their credit card to make the Steam based transaction if they wish, but they will be reimbursed by the site via a PayPal transfer which does not go through Steam.

Yes, but there is no proof that the PayPal transaction is in any way associated to the Steam gift; if we start using a centralized hub with a rating system, transaction history, Steam and PayPal usernames things can get really ugly really fast because there is a trail of money and proof of intent of breaching the TOS.
Maybe nothing will happen in the beginning but as the things gets traction and more and more people start using it it will become known to Steam. From that point you can imagine how easily the accounts are going to be banned and legal action taken.

I wasn't imagining anyone posting their steam names on the site, or their paypal info.
that information would be private.

Except that even then, Valve would not legally have access to the payment histories of transactions that didn't involve them. But yes, any such site -- if public -- will almost certainly wind up with action against them, such as a C&D or disabled accounts.

The information doesn't have to be publicly visible for a site admin to handle such verifications if they are necessary. But even then, you can never be sure that the owner of one Steam account isn't also the owner of another.

The transferring-money-for-a-gift is not looked down on by Steam by the way, it goes on at their cesspool of a forum all the time and they don't seem to care. And why would they? They're still getting fat off people.

Mmmm, the Steam forums. Such a fun place.

I'd love to get started on this, but I would need some help.