virtualbox from the Ubuntu archive for trusty has no dependency on linux-headers. You're using a non-Ubuntu package, as can be seen from your apt log above.
** Changed in: apt (Ubuntu) Status: New => Invalid -- You received this bug notification because you are a member of Ubuntu Touch seeded packages, which is subscribed to apt in Ubuntu. https://bugs.launchpad.net/bugs/1472351 Title: autoremove unable to sweep any linux-headers packages Status in apt package in Ubuntu: Invalid Bug description: Hi, i'm using Ubuntu 14.04 LTS and I have an issue with autoremove command. The point is that I have Virtualbox package installed that has following tag: Recommends: linux-headers As a result autoremove marks all of linux-headers-*/linux-headers-*-generic packages as required and declines to sweep them. Please check the attached log file. To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/apt/+bug/1472351/+subscriptions -- Mailing list: https://launchpad.net/~touch-packages Post to : touch-packages@lists.launchpad.net Unsubscribe : https://launchpad.net/~touch-packages More help : https://help.launchpad.net/ListHelp