Если допустим удалить историю с гугла, остается ли она где-нибудь?

в ихнем кеше одназначно остаётся

жена смотрит не смотрел ли фотки баб в соц сети ?)))

ну можно как-то нарыть, но это очнень сложно.... и обычным ользователям такое не под силу.. . только как говорится ФСБ!

Гугл это вообще то амеровская кантора. Скорее всего на ихних серваках что то должно остаться. По крайней мере сохранить и отслеживать это технически не сложно.

Да, остается видно провайдеру

Да, куки используй программу Ccleaner. Эта программа полностью удалит все, что тебе надо.
P.S провайдер видит все