You're right. Just like Adam Back's email proof of work proposal.
Such an integration would come at the network level. All Yggdrasil nodes, for example, would need to not pass a packet unless there is a proof of work attached with similar difficulty to other packets. This is the only way to reduce spam.
I don't see how this blends in with monetization of maintaining the network however. Would there also need to be routing fees, or is a computer network just considered a community investment at this point?