Contextual ads is the answer. You sell shoes, go and advertise on fashion related sites. I don't want to see a shoe ad while I'm browsing a gaming site just because I did some relative search a week ago. It's so fucking annoying and I never understood why Google never bothered to try some alternative too. I don't mean completely replace behavioral targeting but at the very least try some contextual one too.