I have found that add format helps. I have tried the approach of having ads reflect the pages appearance, but click throughs dropped. I have read people advocating this, but it hasn't worked for me. Perhaps people feel you are trying to fool them or they just don't notice the adds.
I have now made my ads look a bit gawdy, red and green, though on white background and I seem to have better click through rates.
I also moved some adds to the middle of an editorial - they don't have a border, but are quite standard, and the ctr was helped a lot!
I still havn't solidified my thinking about all this, but would like to hear other web worlders.
Ad format and placement can make a huge diffeece in performance. Ads that blend in with the page have not performed well for me. So, like you, I have made them stand out a bit. I use rotating background colors for my ads and that seems to help a bit. I think that helps because many of my visitors look at many pages during a single visit.
There is a lot of common opinion that placing the ads "above the fold" increases performance. I haven't found that to be consistently accurate either.
In the end, general rules about this are just that, general.
Webmasters need to keep experimenting untill they find what works on their specific sites.
Playing around with the different ad formats can have a significant impact on your earnings and EPC. I use to use the 120x600 skyscrapers with no border - and had a relatively good EPC overall. But, I played around with the 160x600 skyscrapers and immediately had a .5% increase in EPC right out of the gate - and that gain continues to hold more than a month later. Better yet, not only are clicks up, but the larger ads just plain look better in my overall site design.