Protect against labels not matching regex

We had an issue where some labels were not matching the provided regex
and we were blindly assuming it would always match.