And how do they prove to me they (and no 3rd party providers) aren't actually storing the data? I simply don't trust companies telling me they won't store something, so to me the only acceptable option is the data to never leave my device.

If third party does verification with ZKP, you only need to trust that third party. The company that requires verification will not have any data to store.