Last week I ran Ad-Aware AE in full scan mode and got the "removal successful" message for the 14 tracking cookies found. Then immediately I ran SE in smart scan mode (with the last 30.03.2009 definitions update) and it found 13 tracking cookies - 12 of them are the same just "removed" by AE!
AE in full scan mode scanned 111,639 objects in 1:24:03 hs. SE in smart scan mode scanned 140,428 objects in 05:49 min.

This week I ran both in smart scan mode. AE found (and "removed") 6 tracking cookies. Immediately after that, I ran SE and it found 12 tracking cookies, including the 6 "removed" by AE.

I wonder if AE really works.

I'm not sure about cookies, but there was a similar problem happening with malware removed. The malware was quarantined, not deleted, and AV scans were picking up the signatures of the items in quarantine.

Question, did you ever check your cookies after the scan/rescans to see if they're there? By process of elimination, it would be nice to know if AE is failing to remove cookies or if SE is reporting false positives.

BTW, how do you have both SE and AE installed? Installation of AE is supposed to remove prior versions.