Group key-value pairs in chunks no longer than specified limit
def group(url,D,limit):


D is a bad parameter name because it doesn't follow the python convention: lowercase_with_underscores, and because it a pointless abbreviation.

    if len(D) == 0:
        if len(url) &lt;= limit:
            yield url
            return
        else:
            raise ValueError("url is longer than limit")

    if len(url) &gt; limit - 2:
        raise ValueError("url is too long to be able to hold any key-value pairs")


Is this really a useful check? Two characters is probably not enough to actually hold any of the pairs. You probably don't catch anything here you wouldn't already catch

    for i,(key,value) in enumerate(D.iteritems()):
        if i == 0:


enumerating for the sole purpose of special casing the first entry is rather gross. 

            old = url
            new = '{url}?{key}={value}'.format(**locals())
            continue


I discourage the use of continue. It's almost always better to put things in an else block

        new, old = '{new}&amp;{key}={value}'.format(**locals()), new


Use of locals() is discouraged. It encourages sloppy coding and forces python into a slower compatibility mode for that function. 

        if len(new) &gt; limit:
            if len(old) &gt; limit:
                raise ValueError("String '{old}' is longer than GET query limit.".format(**locals()))
            yield old
            old = url
            new = '{url}?{key}={value}'.format(**locals())
    if len(new) != len(url):


In which case would this be false?

        if len(new) &gt; limit:


Why is this check inside the other check?

            raise ValueError("String '{new}' is longer than GET query limit.".format(**locals()))
        yield new


Of course, you've already noted the duplicated code here.

Here's my take on reworking it:

def blocked(items, limit, seperator):
    """
    items is a list of strings, to be joined with seperator.
    Produces a generator of strings, each with a length &lt;= the limit
    """
    current = []
    current_length = 0
    for item in items:
        length = len(item) + len(seperator)
        if length &gt; limit:
            raise ValueError('{} cannot fit'.format(item))
        elif length + current_length &gt; limit:
            yield seperator.join(current)
            current = [item]
            current_length = length
        else:
            current.append(item)
            current_length += length
    yield seperator.join(current)

def group(url,data,limit):
    if len(url) &gt; limit:
        raise ValueError('{} is longer than the limit of {}'.format(url, limit))

    pairs = ["{}={}".format(k,v) for k, v in data.iteritems()]
    for block in blocked(pairs, limit - len(url), "&amp;"):
        if block:
            yield '{}?{}'.format(url, block)
        else:
            yield url