Use esta linha:
cat /var/log/dpkg.log | grep "2016-05-05" | grep "remove" | grep -v "startup"
E para colocar em um arquivo:
cat /var/log/dpkg.log | grep "2016-05-05" | grep "remove" | grep -V "startup" > removed-files.txt
Certamente, há várias maneiras, e talvez até mais elegantes, de fazer isso. Se você indicá-las, adicionarei à minha resposta aqui.