Вы можете использовать BeautifulSoup insert , чтобы добавить элемент в нужное место:
from BeautifulSoup import BeautifulSoup
soup = BeautifulSoup(html)
for link_tag in soup.findAll('a'):
link_tag_idx = link_tag.parent.contents.index(link_tag)
link_tag.parent.insert(link_tag_idx + 1, '<b>OK</b>')
Это работает для приведенного вами примера, хотя я не уверен, что это единственный илисамый эффективный метод.