We are looking for either a MySql existing solution, third-party
solution or code to handle the following problem:

We have two linux servers in a master/slave relationship using MySql
4.0. Every once in a while the MySql replication halts because of some
problem (eg: mysql query error, human error, etc). I need to have an
email notification sent out of the replication stops. Currently we
sometimes wait hours or even days before realizing the replication has
stopped. Can you advise?

Try Nagios www.nagios.org. I am using it to monitor and send email
alerts if replication process or mysql itself goes down.