I'm reading this to mean by adding package dependencies where missing,
right?

This is actually Kinda Hard, because /var/log/messages is really more an
artifact of our default rsyslog config than part of any package. If we
wanted to say that some syslog service always provides that file, we should
make it clear that changing it is actually not available for end-user
configuration and should never been changed. We've never done that.

So, adding "Requires: rsyslog" isn't _really_ sufficient. We could ship the
/var/log/messages configuration in a subpackage that goes into
/etc/rsyslog.d/ and ask packages which expect /var/log/messages to require
that.