Longest-match lookup via nested dicts
class CommandStorage(object):
    """Stores multi-part commands.

    Performs fast lookups returning the command and any arguments which were
    not part of the command.
    """

    def __init__(self, commands={}):
        self._root = {}
        self._commands = {}


Do you really need to store all the data twice?

        for cmd, func in commands:


That should be commands.items(), guess you've never used the parameter

            self[cmd] = func

    def _lookup(self, line):
        parts = line.split(' ')
        found = None
        found_container = None
        container = self._root
        command_parts = 0
        for i, part in enumerate(parts):
            if part not in container:
                return found_container, found, parts[command_parts:]
            container = container[part]


The recommended way to structure something like this to catch the KeyError, so:

try:
    container = container[part]
except KeyError:
    return found_container, found, parts[command_parts:]
else:
    proceed


As it stands, your code looks up the container[part] twice.

            if None in container:


Using None to store the actual value is counter-intuitive. That's not what None usually means.

                found_container = container
                found = container[None]
                command_parts = i + 1


Having these three pieces of data feels ugly.

        return found_container, found, parts[command_parts:]


I think the problem is your data structure. Your collection of dicts of dicts of dicts is tricky to navigate. 

    def __setitem__(self, cmd, func):
        container = self._root
        parts = cmd.split(' ')
        for part in parts:


I'd combine these last two lines

            container = container.setdefault(part, {})
        if None in container:
            raise ValueError('Command %s already exists' % cmd)
        container[None] = func
        self._commands[cmd] = func

    def __getitem__(self, line):
        return self._lookup(line)[1:]


I think this is a bad idea. This function doesn't act like [] typically acts in python. So just make this a regular method

    def __contains__(self, item):
    def __delitem__(self, cmd):
    def __iter__(self):
    def __len__(self):
    def __nonzero__(self):
    def iterkeys(self):
    def iteritems(self):
    def itervalues(self):


You've implemented all these functions to make it act like a dictionary. But its not a dictionary. Unless the object is designed to provide the features of a dictionary, don't attempt to provide the dictionary interface. 

    def __repr__(self):
        return '&lt;CommandStorage(%r)&gt;' % self._commands.keys()


Here's how I'd approach it. Don't use nested dicts, just store everything in one dict. __setitem__ becomes trivial:

def __setitem__(self, cmd, func):
    parts = tuple(cmd.split(' '))
    if parts in self._commands:
        raise ValueError('Command %s already exists' % cmd)
    else:
        self._commands[parts] = func


Then, _lookup becomes:

def _lookup(self, line):
    parts = tuple(line.split(' '))
    # start with longest match, work backwards
    # first match found will be longest match
    for index in xrange(len(parts), -1, -1):
        try:
            function = self._commands[parts[:index]]
        except KeyError:
            pass # no match found, try next one
        else:
            break # match, stop search
    else:
        function = None # if all else fails, report None as function

    return function, list(parts[index:])