Digital communication increasingly underpins identity, financial transactions, and regulatory compliance. In many settings, possession of a DKIM-signed email serves as evidence of account control, transaction confirmation, or institutional affiliation. Yet demonstrating such properties typically requires revealing the full email or relying on centralized intermediaries, introducing privacy risks and additional trust assumptions. A framework called ZK Email addresses this limitation by applying zero-knowledge proofs (ZKPs) to email verification, enabling publicly verifiable proofs of authenticity while preserving message confidentiality. However, its existing implementations struggle to support complex, real-world messages due to the inefficiency of regular-expression verification over structured formats and rich alphabets. We address this limitation with a new ZKP system for generalized regular expression (regex) matching that replaces in-circuit automaton simulation with efficient path verification over ε-free NFAs, yielding prover complexity linear in the input length and independent of the regex complexity. This approach enables practical validation of expressive standard structures required for full DKIM-signed email verification. By integrating our constructions into ZK Email, we obtain an enhanced system that combines (i) DKIM signature verification, (ii) an arbitrary-length SHA-256 circuit with partial precomputation for rsa-sha256 under RFC 6376, and (iii) a general-purpose regex primitive enforcing structural constraints over email headers and body. We formalize the associated zero-knowledge relations and analyze their security under adversarial models. We implement the system (over 40,000 lines of code released under MIT) in Circom and Noir, targeting groth16 and ultra_honk backends, and evaluate it in both client-side and zkVM (SP1) deployment settings. Experimental results on a commodity hardware demonstrate substantial efficiency improvements over prior DFA-based approaches, achieving 2–6× in proving time, while supporting a significantly richer class of regex languages.