For some reason, kmess-1.1 got by just fine without kdenetwork. kmess-1.2.1 needs mimelib/mimepp.h Google search revealed that the file belongs to kdenetwork. How I discovered this? I am actually a heavy GNOME user and a light KDE user.
Installing kdenetwork installs the missing headers.
You're right, the missing dependency has been added. Thanks for the report.