I've found more info about this. You were right that it was remembering previously paired devices. Logitech has a utility that allows removing pairings (for Windows) and I was able to remove the keyboard.
- Bug#841275: linux: Logitech Unifying Receiver s... Trent Gamblin
- Bug#841275: linux: Logitech Unifying Recei... Ben Hutchings
- Bug#841275: linux: Logitech Unifying R... Trent Gamblin
- Bug#841275: linux: Logitech Unifyi... Ben Hutchings
- Bug#841275: linux: Logitech Un... Ben Hutchings
- Processed: Re: Bug#841275: linux: Logitech... Debian Bug Tracking System
- Processed: Re: Bug#841275: linux: Logitech... Debian Bug Tracking System
- Bug#841275: linux: Logitech Unifying Recei... Ben Hutchings
- Bug#841275: marked as done (linux: Logitec... Debian Bug Tracking System
- Bug#841275: linux: Logitech Unifying Recei... Trent Gamblin