Я так понял, что если прокси не анонимный, то мой настоящий АйПи остается на сайтах?

Я тоже так думаю, вот поэтому наверное, что в поисковике ищешь, то потом у тебя и в рекламе появляется. Вот я искала инфу про авиабилеты, теперь это добро висит у меня справа страницы!

нет ...у прокси свой у вас свой ( который через прокси подключен)

если подключение идет через любой прокси или сервер с NAT (трансляцией адресов) то IP можно вычислить только из логов твоего провайдера
А информеры, реклама и прочая дрянь работают через cookies загружаемые в твой браузер