I took a look to what other languages do, and it turned out that:

perl escapes [^A-Za-z_0-9] [0];
.net escapes the metachars and whitespace [1];
java escapes the metachars or escape sequences [2];
ruby escapes the metachars [3];

It might be OK to exclude _ from the escaped chars, but I would keep escaping all the other non-alnum chars too (i.e. match perl behavior).

(FWIW, I don't think re.escape() is used in performance-critical situation, so readability should probably be preferred over speed.)

[0]: http://perldoc.perl.org/functions/quotemeta.html
[1]: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regex.escape.aspx
[2]: http://download.oracle.com/javase/1.5.0/docs/api/java/util/regex/Pattern.html
[3]: http://www.ruby-doc.org/core/classes/Regexp.html