Update: Whoops! Looks like Christoforo suggested this first. Not sure why that post's code is all struck out though.

Set::CrossProduct to the rescue:

use strict;
use warnings;

use Set::CrossProduct;

my %hash=('ID' => {
                  'key1' => [ qw/ key1_val1 key1_val2/ ],
                  'key2' => [ qw/ key2_val1 key2_val2/ ]
                  }
          );



foreach my $id ( keys %hash ) {

    my $keys = $hash{$id};

    my $set = Set::CrossProduct->new( [ values %$keys ] );

    print join( ', ', $id, @$_ ), "\n" while $_ = $set->get;


}
[download]

Results in

ID, key2_val1, key1_val1
ID, key2_val1, key1_val2
ID, key2_val2, key1_val1
ID, key2_val2, key1_val2
[download]

Not exactly the order of your requested output, but that's because your keys are in a hash.