Удаление действий не имеет особого отношения к анонимности. Анонимность это когда действия есть, но не выяснить кто их сделал :)
По вопросу:
1) Удаление действий на своем компьютере (чистка истории в браузере, например) восстанавливается в общем случае довольно просто, если придет экспретиза.
2) Все действия (посещение сайтов, скачивание файлов) хранятся у провайдера и владельца сайта. К ним у вас доступа нет - значит там тоже хранится информация о ваших действиях (обычно это: время захода на сайт, используемый браузер, IP адрес, путь и метод запроса (например, открытие example.com/cats/). Удалить их не выйдет (обычно администраторы сами очищают эту информацию с течением времени - раз в несколько месяцев / лет)
3) По поводу публикации фотографий и иных материалов в интернете. Попробуйте залить фотку в ВК, открыть саму картинку (начинается с pp.vk.me), оставить вкладку с фото открытой и удалить фотографию через интерфейс ВК (вернувшись на предыдущую вкладку). Потом вернуться на вкладку с pp.vk.me и обновить страницу. Как видите - фото останется на месте (по полному пути), несмотря на то, что вы ее только что удалили из интерфейса (это связано с особенностью работы крупных ресурсов, т.е. не только ВК так поступает).
P.S. Большой брат всегда следит ^^
иллюзия