Not sure how MPLS would come into this particular problem.
But I see 2 possibilities, 1: The gateway is not reducing the TTL by 1 thus the packet goes trough without expiring, or 2: The gateway is responding to the TTL expired with a different one of its IP addresses and the first Verizon hop you see is probably really it.