На примере моего провайдера - хранят не только привязку к одному маку, но и ВСЕ маки, под которыми выходили с моего IP-адреса. Кроме того, они знают с какого порта роутера кто выходил и с каким IP/MAC-адресом, т.е. е знают территориальное месторасположение.