Как вариант (не единственно возможное решение):
pattern = r'(<a rel=")(.+?)(">)'
splitted = re.split( pattern, html_str )
# splitted == [ '<html>...', '<a rel="', 'http://site.com/image1.jpg', '">', '<div>...', '<a rel="', 'http://site.com/image2.jpg', '">', ... ]
urls = splitted[2::4]
# urls == ['http://site.com/image1.jpg', 'http://site.com/image2.jpg', ... ]
Далее проходите по splitted в цикле с шагом 4, и, если image не удовлетворяет условию, удаляете текущие
[ '<a rel="', 'http://site.com/image2.jpg', '">' ] из списка splitted или заменяете их на что-то (например, на "название ссылки").
А после чистки:
cleaned_html_str = ''.join(splitted) 
