Конечно, могут. И постоянно делают это, а кое-где (в РФ, например), они обязаны это делать :) (провайдеры).
Конечно, ssl защищает, но... есть такая штука как бампинг :) и в связи с повсеместной ssl-изацией я думаю, мы очень скоро увидим ее повсеместное применение в масштабах государства. Если провайдер/VPN/прокси для начала работы требует неважно по какой причине поставить сертификат - он точно будет бампить :) Если нет - могут писать логи, что тоже может быть интересным для определенных лиц...