I agree, this is an accademic issue, and in some cases the additional layer of abstraction is not needed. Being aware of the shortcoming is one thing, but knowing whether it matters is more important

I consider your point regarding YAGNI to be valid and as such I'd be tempted to write the following more pragmatic approach:

<?php

class PasteHash
{
    public function create(Paste $paste, PasteService $service)
    {
        $seed = $paste->language . $paste->timestamp . $paste->content;
        do {
            $seed . = uniqid();
            $hash   = hash('sha1', $seed);
        } while ($service->exists($hash));
        return $hash;
    }
}

class MongoPasteService implements PasteService
{
    protected $collection;
    protected $hash_builder;

    public function __construct(MongoCollection $collection, PasteHash $hash_builder = null)
    {
        $this->collection = $collection;

        $this->hash_builder = $hash_builder ?: new PasteHash();
    }

    public function create(Paste $paste)
    {
        $hash = $this->hash_builder->create($paste, $this);
        $paste->hash = $hash;
        $this->collection->save((array) $paste);
        return $paste;
    }

    public function exists($hash)
    {
        /* .. check if paste exists .. */
    }
}

The above code does not introduce an additional abstraction layer but still offers me all the benefit of being able to mock the hash generation. The big assumption in the code above is that PasteHash is re-used; otherwise I'd just use a method and test that using the test cases for this class.

By using statics you require every unit tests that involves this hash creation to test the hashing code, to not test the hashing code at all or pick a leading implementation where you test the hashing code (which is unsafe). In my opinion the static helper hurts testability and provokes abuse of the helper class.

I get your point, Mike -- but I have another question: would you make the same comment if a function were used versus a static method? In both cases, the implementation would be tied to a specific set of code -- and yet I've not heard anybody talk about the LSP with regards to functions. (I'm truly curious, as I don't have an answer here.)

I would have made the same, or at least a very similar, comment.

As I see it, functions introduce the same issues as static methods; they induce a hard and untestable coupling between two structural elements.
For example: if I were to write a unit test for the create method in your example I would be required to test whether the has is correctly generated and thus write testing code that checks the createHash() static method. The same thing would happen if createHash() would be a function and thus the same comments apply.

Please note that this comment even applies to Traits; these are untestable, deeply coupled bits of code.

With regards to LSP and functions; in my opinion LSP is only applicable to objects as you cannot substitute methods or functions (monkeypatching not included in this statement); just objects. To even be a bit bolder: LSP applies to object oriented programming, (userland) functions are to be considered procedural programming. As such these two are hard to unite.