Zero-BTC transaction fees, service-specific mining pools and external compensation
Every mining pool can select (valid) transactions for confirmation on basis of whatever criteria they want. If the mining pool had an agreement based on direct payment by those wanting to use the notary service, they could prioritize confirmation of document hash transactions.

The criteria of selection would then perhaps be that they get the transaction from their customer with the request to confirm it.

However, this scheme would only make economic sense for the mining pool, if confirming the notary transactions was more valuable to them than the fees paid by regular transactions. So, in a sense, those notary transactions would have to compete with a similar value level as regular fees anyway.

With 0.1% of the global mining power, the expected time until the pool finds a block is 10000 minutes, which is pretty close to one week. If the pool were to maintain their 0.1% hashrate, it would have a chance of 1 - exp(-4) = 98.1% chance to find at least one block in four weeks.

Something very similar is already happening: BTCC is running a service called BlockPriority that prioritizes transactions of BTCC customers.



That said, it is unclear to me why one would want to encourage users to create bloat on the Bitcoin blockchain. It would make much more sense to create a Merkle tree from all documents to be confirmed, publish it somewhere online, and just anchor the root of that Merkle tree in the blockchain by paying a single transaction fee.