You can use dict.pop:

 mydict.pop("key", None)

Note that if the second argument, i.e. None is not given, KeyError is raised if the key is not in the dictionary. Providing the second argument prevents the conditional exception.

There is also:

try:
    del mydict[key]
except KeyError:
    pass

This only does 1 lookup instead of 2. However, except clauses are expensive, so if you end up hitting the except clause frequently, this will probably be less efficient than what you already have.

Approach: calculate keys to remove, mutate dict

Let's call keys the list/iterator of keys that you are given to remove. I'd do this:

keys_to_remove = set(keys).intersection(set(mydict.keys()))
for key in keys_to_remove:
    del mydict[key]

You calculate up front all the affected items and operate on them.

Approach: calculate keys to keep, make new dict with those keys

I prefer to create a new dictionary over mutating an existing one, so I would probably also consider this:

keys_to_keep = set(mydict.keys()) - set(keys)
new_dict = {k: v for k, v in mydict.iteritems() if k in keys_to_keep}

or:

keys_to_keep = set(mydict.keys()) - set(keys)
new_dict = {k: mydict[k] for k in keys_to_keep}