I like your solution, but I'm not sure what + is doing in this line:

push @{$groups{ +shift( @items ) }}, shift( @items );
[download]

I found this in perlop

Unary "+" has no effect whatsoever, even on strings. It is useful syntactically for separating a function name from a parenthesized expression that would otherwise be interpreted as the complete list of function arguments.

Is that what you were doing there? Making sure Perl knew that the return value from shift( @items ) was not part of an argument list?