Para enviar msgs entre usuarios, solo crea una tabla en MySQL de mensajes con los campos
MsgID, UsrDe, UsrPara, Mensaje, FechaHora
Y cualquier otro dato que quieras (por ejemplo la IP de quien postea)
Luego haces la bandeja de entrada con un query como:
select * from Mensajes where UsrPara=$miUsrID order by FechaHora desc
Que te parece?
Y para usuarios en linea creo que hay un tutorial por ahi (creo que de Cluster), buscalo en las FAQ o con el sistema de busqueda del foro.
Saludos! y felicidades por hacer tu propio desarrollo en lugar de ir a tomar un Nuke!!