And this really is simple enough that I don't want to reach for regex's for it. That is, I'd write it by hand rather than mess with that.

Well, with re.escape it's not messy at all :

import re

def trim_mailto(s):

  regex = re.compile("^" + re.escape("mailto:"))

  return regex.sub('', s)

With literally means "if you have mailto: at the beginning, replace it with the empty string"

You could do a ltrim function in one line :

def ltrim(s, x):

    return re.sub("^" + re.escape(x), '', s)

Escape will take care of escaping special characters, so the regex escape(x) matches exactly the string "x".