Googling for the problem says that in Device Manager you should see, under "Portable Devices", either "Kindle" or "MTP device", and that those puppies might need a driver update.

You said that it disappeared from device manager altogether. Is there any yellow boo-boo icons, something like "unrecognized device" or something?

Is there a Kindle "application" to install on Windows? Often times, they include the latest device drivers along with the application. You might want to try installing that.