Capital One used atdmt.com which I think, is Avenue-A Razorfish.
I actually worked on the Capital One Internet team for about 6 months. They also used some rather expensive software called Visual Science which tracked internet traffic.
One of the things they did (it might be industry standard, I don't know) was to put unique URLs on all the banner ID and search engine links. So, they would know, based on the URL where someone linked from.
For example, go to
www.google.com and type in "capital one" and then hit search. If you click on the sponsored link, you will see a complex URL with the "external_id=" tag applied to it. This tag, denoted as "WWW_10014_1C1_SEM-Brand_Google_ZZ_ZZ_T_Home" breaks down into various piece parts, which they can use to analyze the link.
For example, the code "10014" represents the search term "Capital One". There are other search terms which are valid, and Google charges a fee based on a complex algorithm which essentially boils down into how popular or common the term might be. For example, paying for a search term like "credit card" is RIDICULOUSLY expensive. They told me. It was something on the order of like $70 per click or something insane like that. Everytime you click on a sponsored link, that company pays Google for that link.
Avenue-A Razorfish received a report (I was responsible for putting it together, among other things) that contained all the link information. I think they managed the providers for Capital One and made sure that the search engines didn't charge Capital One for more links than what Capital One was actually receiving, etc.