Do all outputs have an address associated with them? I guess more specifically, a decodable address?
I have seen transactions on blockchain.info where the address was "unable to decode"
Is there a way to count these?
Also do they stay in the UTXO set forever (since they cant be spent)? Or is there a way to drop these from the UTXO? Are they currently being dropped?
Not every UTXO has an associated address.

An address is really just a shorthand notation for a particular Bitcoin Script. There exist many interesting scripts which do not correspond to an address, but are still spendable under some conditions.

Note that every P2SH output does have associated address, and almost all interestong scripts these days use P2SH.