Do all outputs have an address associated with them?
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.