Agreed. Try to teach those poor souls regex and their eyes will roll right back in their heads.
A "normal" search engine (with its boolean logic AND, OR, NOT) will be quite enough of a logical stretch for them.
Of course you could always hack up the equivalent of KRAUT or JIVE or "Swedish Chef" as a down and dirty translator if you really want to get their attention :-)