> CenturyLink should obviously have some way to add state-specific notifications to customers' bills.

If only there was some relevant piece of data, already required to ensure the bill reaches it's destination, that could help them determine which customers are in which states.

They know billing addresses, and service addresses. They just didn't care.