Hola,
Si la aplicación tiene que "avisar" al usuario, casi mejor que no sea un servicio de Windows, aunque, es posible para estos interactuar con el usuario, no es una aplicación que el usuario pueda "controlar", si no usa el "Gestor de servicios de Windows", o tú mismo preparas un "controlador" para el mismo.
Para que una aplicación se inicie junto a Windows, puedes usar, por ejemplo, el registro de este. En el apartado de trucos
tienes uno que te enseña cómo hacerlo. Respecto de que tu aplicación se inicie en la bandeja del sistema, la palabra clave es "TrayIcon". Busca información en estos foros, por ejemplo, puesto que encontrarás diferentes soluciones, desde pegándote con la API de Windows, a componentes de terceros que ponen las cosas mucho más sencillas.
Y respecto a la base de datos... me temo que no se me ocurre más que estar pendiente de ella, es decir, de hacer una consulta cada cierto tiempo, en segundo plano, sin intervención del usuario, mientras tu aplicación se ejecute. Haces una consulta en que cuentes los registros de una determinada tabla, por ejemplo, y, si el número de estos es mayor que la última vez que lo comprobaste, "avisas" al usuario.
PD. Muevo el hilo a "Conexión con bases de datos", puesto que la tiene, y creo que no sólo con MySQL.
