There seems to be agreement that a paper wallet is safe, but how long term?
Impossible to know. It would be best to keep yourself aware of any major new developments in Bitcoin if you are holding any bitcoin. In general, a paper wallet (if created in a safe manner) should be safe until mathematicians manage to completely break all three of ECDSA, SHA-256, and RIPEMD-160. I'll be surprised if all three of those are completely broken to the point of being reversible in less than a decade.
Do wallet updates effect the paper wallet?
While not impossible, what would be more likely than that is for the current cryptography to become weakened with new mathematical developments. The bitcoin protocol would be updated with new cryptography, and your old paper wallet (while still supported by the new protocol) would become vulnerable to theft.
Should I keep a redundant set of usb's with the program that created the paper with the paper (in case the software goes through some form of evolution)?
That wouldn't hurt, but it isn't likely to help. If the protocol changes in a way that makes it impossible to spend your bitcoins (extremely unlikely), then your old program won't be recognized as valid by the rest of the network.
Does the paper wallet keep track of all of the different receive addresses?
Not usually. Usually, a paper wallet only has a single receiving address.
It just seems odd to me that a single QR code is going to be able to hold enough information to recreate my wallet.
The single QR-Code will most likely hold enough information to recreate a single receiving address. If you want multiple receiving addresses, then each one will have it's own pair of QR-Codes.
And of that, once you create the paper wallet, I assume that you destroy the digital one. If it is still around and falls into the wrong hands, the paper wallet would quickly become useless.
The paper wallet is generally created separate from the digital one. It has its own address that doesn't eve exist in the digital wallet. You send the bitcoins from your digital wallet to the paper wallet. Therefore, there aren't any bitcoins in the digital wallet for anyone to steal. As such, there is no need to destroy the digital wallet. If it falls into the wrong hands it is useless (since it doesn't contain any of the bitcoins.
Wow. Hitting the delete key on that file is gotta be hard to do.
Deleting an empty wallet isn't a very difficult thing to do. Trusting that the paper wallet receiving address matches the paper wallet private key, and sending the bitcoins to the paper wallet receiving address can take some faith though.