> If you split into multiple parts, each part of the key is useful: it lets you reduce your search space by however many bits of the key you have.

That doesn't have to be true. Rather than splitting an AES key K into substrings, a better approach is to choose n parts such that:

    K_1 ^ K_2 ^ ... ^ K_n = K

None of the component K_i will reveal any information about K without knowledge of its peer components.