Portanto, o lxml possui um recurso muito útil: make_links_absolute:

doc = lxml.html.fromstring(some_html_page)
doc.make_links_absolute(url_for_some_html_page)

e todos os links no documento são absolutos agora. Existe um equivalente fácil no BeautifulSoup ou eu simplesmente preciso passar pelo urlparse e normalizá-lo:

soup = BeautifulSoup(some_html_page)
for tag in soup.findAll('a', href=True):
    url_data = urlparse(tag['href'])
    if url_data[0] == "":
        full_url = url_for_some_html_page + test_url