Deriving from concrete, non-polymorphic, classes is typically a bad idea. If a class doesn't have a virtual destructor, it wasn't designed with inheritance in mind (compare to inheritable standard library classes like streams, buffers, and facets)
In this case, because you don't provide rebind, parent class rebind is selected, and parent (std::allocator<K,V>) is used for all allocations done by a container that's instantiated with this PoolAllocator<K,V>.
I don't see any checks to ensure "PoolAllocator::bytes's" alignment. Most modern operating systems try to return aligned pointers, but this is not always the case. On some CPUs, attempting to read misaligned data can cause a complete failure of the CPU which requires a restart. Granted, the CPUs we have now are capable of handling misaligned addresses, but it's not without a performance penalty. If you want performance, align your data.
Based on what I've seen in the implementation of "std::malloc_allocator" and "std::new_allocator", neither assure alignment of the allocated memory, which leads me to believe that the implementers of the aforementioned classes assume the OS will align the memory for them.
In your implementation of "PoolAllocator::deallocate( )", why are you throwing exceptions left, right and centre? Throwing exceptions is expensive and you should only throw them when something really has gone wrong. I personally think you're misusing exceptions in your code.
Also, what's the purpose of "PoolAllocator::max_size( )"?
Actually, alignment is not always respected even though the standard says so due to compiler bugs. In addition, even if "new" and "malloc( )" do return aligned memory, it's not guaranteed to be sufficiently aligned for the program's needs; alignment to a CPU cache-line springs to mind.
How do we know that Catfish's allocator is not a special case? We don't know what sort of data is going to be stored. In addition, the allocator needs respect special alignment requirements for types that it may be required to store at some point in the future if it [the allocator] has any chance of being flexible and reusable.