If the regexps come from users, will I have a taint problem?

Unless you explicitely enable use re 'eval'; you won't have problems where tainting can help you prevent getting damaged - the user can't inject arbitrary code.

I am worried about intentional or unintentional ill-effects beyond an error.

And you should! No tainting is going to protect you from a regexp that will run "forever", or that's going to exhaust your memory or stack size in a quick fashion. There's no easy defensive against this.

Would qr help with this? Or how about Safe ?

No, and no. Read the manual page of Safe.pm about things Safe doesn't protect you from - the first things mentioned are "Memory" and "CPU".

How could a user specify a regexp meaning, "Any string that does not have the phrase 'foo' in it?"

/^(?:(?!foo).)*$/s;
[download]

Abigail