Package names are handled as described in the documentation for
apt-get install (yes, it’s not obvious):
If no package matches the given expression and the expression contains one of '.', '?' or '*' then it is assumed to be a POSIX regular expression, and it is applied to all package names in the database. Any matches are then installed (or removed). Note that matching is done by substring so 'lo.*' matches 'how-lo' and 'lowest'. If this is undesired, anchor the regular expression with a '^' or '$' character, or create a more specific regular expression.
Strictly speaking, this check comes after a glob performed on the available package names — so package specifications are first checked for an exact match, then checked for glob matches (using
*), and if that doesn’t find anything, and the package specification contains
*, interpreted as regular expressions. (You can see the globbing behaviour by running
apt-cache policy 'firefo?', which matches using only a glob, and then
apt-cache policy 'firefox?', which ends up using a regular expression.)
apt-cache policy 'firefox*' matches using globs. If you want to force it to match using a regular expression, you can use something like
apt-cache policy 'firefox.*' instead; check for
mozilla-firefox in the output to see if the expression is matched as a glob or as a regular expression.
apt-cache search is documented explicitly as handling regular expressions because its arguments are always treated as regular expressions.
Given the kind of regular expressions
apt supports, excluding
-l10n- is probably impossible; see this SO answer for details.