http://uidh.crud.net/ also says "did not receive X-UIDH header."
California, Verizon Wireless, Business Account, not on contract.
EDIT: Now an hour later, the headers DO appear. No setting to disable on the VZW site though.