yo sulo poner las imagenes que uso en el mensaje en mi servidor y poner el path de la imagen de manera absoluta.
ej:
Código PHP:
$mensaje="<html><head></head><body bgcolor=\"#0000ff\">";
$mensaje .="<font face=\"Arial\" size=6>Prueba HTML </font>";
//
$mensaje .="<img src='http://www.miserver.com/imagen.gif'>";
//
$mensaje .="</body></html>";