Det gør den besøgendes browser helt automagisk, når den viser din side med linket...

#1 -> men den gør det forkert hvis man kommer ned i undermapper på sitet. I hvert fald med en relativ sti.

Du kan også vælge at bruge en absolut sti, så gør den det korrekt, som #1 skriver.
<a title="Titel" href="/underside2">Link til intern side</a>

En funktion kunne se sådan ud:
function MyLink($link) {
  return 'http://www.navnpåhjemmeside.dk/ (...)
}
<a title="Titel" href="<?php MyLink('underside2');?>">Link til intern side</a>

Men det gør vel også det hele komplekst at kode, fordi du skal oprette linket gennem php hver gang. Værd sikker på du har behovet, eller bliver du træt af det. En absolut sti fungerer også fint.

#1 - Det er jeg klar over, men af hensyn til SEO vil jeg gerne have den fulde sti.

#2 - Det skal helst være en funktion der kan skanne min tekst og fungere automatisk. Jeg har ikke overskud til at tilføje en funktion hver gang jeg skriver et link.

Jeg forestiller mig noget ala:

//funktion der skanner mit recordset

function addFullURL (
gennemløb koden og tjek om der er link uden "http://" - hvis ikke, så tilføj dette i linket
)

echo addFullURL($_ROW['message']);

Det er bare lige hvordan det skal kodemæssigt skal fungere.