Does it really make sense to deprecate regexps for apt-cache search? In that case, I think you're very unlikely to want a literal match.