Problemas con Sendmail

[sexto]

No sabía si poner este post aquí en Programación Web, pero realmente el problema lo tengo con el Sistema Operativo, no con el código de la Web...

Me pasa lo siguiente: Tengo un servidor con Ubuntu 10.10, lo uso para alojar Webs, entre otras cosas, aunque no está fijo, ya que solo están ahí mientras son programadas. El caso es que necesito mandar mail desde esas Webs, y ahí viene mi problema.
He instalado Sendmail (tengo que usar la función mail de PHP, no otras cosas raras) y me da varios problemas. El principal es que no me funciona... después, si yo hago un documento PHP sencillo, simplemente con la función y sus parámetros, se queda cargando durante 2 o 3 minutos y cuando termina no lo manda (he probado ha meter la función en un if, y efectivamente me hace el else, pero al rato).
También he probado a poner el comando sendmail en consola, y lo mismo, se queda pillado durante un buen rato pero luego no manda nada.
Si paro sendmail y luego lo vuelvo a arrancar también me tarda un montón en arrancarse.

Que le puede estar pasando?
Que hago para que funcione?

Muchas gracias.

[Slava_TZD]

Sin un mensaje de error o algo por el estilo, es complicao' saber donde mirar...Los logs deberian ser el primer lugar donde buscar algo anormal.

[sexto]

Es que no me da ningún error... Simplemente no lo manda.
En que log escribe el sendmail?

EDITO: He probado a desinstalar Sendmail y probar con Postfix, tampoco me funciona, pero el mail intenta salir al exterior, creo. El mensaje es el siguiente:

Código [Seleccionar] Expandir

delivery temporarily suspended: host mx00.1and1.es[212.227.15.134] refused to talk to me: 554 RBL rejection: http://www.spamhaus.org/query/bl?ip=(mi IP)

Si lo intento mandar a una cuenta de Gmail me pone:

Código [Seleccionar] Expandir

host mxintern2.kundenserver.de[212.227.126.205] refused to talk to me: 421 mxintern.schlund.de: Too many concurrent SMTP connections; please try again later



EDITO2: Ya lo he conseguido solucionar (Aunque al final he usado Postfix)

[Slava_TZD]

EDITO2: Ya lo he conseguido solucionar (Aunque al final he usado Postfix)

Entonces no ha sido una solución al problema original 

De todas maneras si pones como lo solucionastes puede que en un futuro alguien con el mismo problema encuentre el post y le valga de algo.

[sexto]

Realmente hice tantas cosas que no se cual de ellas fue la que hizo que funcionara...