Imitate The Deck (http://decknetwork.net/). They produce beautiful, low impact, relevant ads which I frequently consider carefully and often click-through on. They do an amazing job and I've deliberately reduced the power of my adblock blacklists to see those ads.

An example ad: http://hivelogic.com/

They're clearly not even attempting to scale, but they have the ideas that -- if brought to scale -- could make advertising less sinful.