This is nearly determanistic and fast, and I believe all possible outcomes are possible (d'uh!:), and I don't think that there is any particular bias. I'm not sure about the fairness though.

#! perl -slw
use strict;
use List::Util qw[ sum ];

sub gen {
    my $constraints = shift;
    my @rands = map $_->{ mid } - $_->{ sd }, @$constraints;
    my @limits = map $_->{ mid } + $_->{ sd }, @$constraints;
    my $remainder = 100 - sum @rands;
    while( $remainder ) {
        my $target = int rand @rands;
        my $addition = 1+ int rand $remainder;
        next if $rands[ $target ] + $addition > $limits[ $target ];
        $rands[ $target ] += $addition;
        $remainder -= $addition;
    }
    return @rands;
}

my @constraints = (
    { mid => 20, sd => 15 },
    { mid => 30, sd => 25 },
    { mid => 50, sd => 10 },
);

print join ' ', gen( \@constraints ) for 1 .. 20;

@constraints = (
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
    { mid => 10, sd => 5  },
);

print join ' ', gen( \@constraints ) for 1 .. 20;

__END__
C:\test>598736-2.pl | more
12 47 41
13 29 58
25 35 40
27 33 40
11 33 56
15 27 58
25 35 40
32 18 50
34 23 43
14 35 51
24 16 60
5 43 52
13 47 40
29 14 57
33 8 59
23 37 40
29 11 60
7 33 60
5 41 54
33 9 58

10 10 5 8 12 11 5 15 12 12
7 5 11 14 15 7 6 9 11 15
5 5 9 13 14 7 11 12 10 14
14 13 8 14 9 5 12 5 14 6
13 5 14 15 10 5 15 9 9 5
5 10 5 14 13 11 15 13 5 9
5 10 13 14 14 5 13 12 5 9
12 9 14 11 7 14 8 15 5 5
14 14 5 14 5 14 8 5 12 9
15 14 12 15 7 5 10 8 9 5
14 5 12 10 15 14 5 5 9 11
12 12 10 9 9 6 15 8 14 5
11 15 9 13 10 6 15 6 5 10
15 12 14 8 5 10 11 5 15 5
5 13 14 6 14 12 12 14 5 5
14 5 12 14 15 8 5 7 15 5
14 8 14 13 15 5 5 14 5 7
13 7 8 5 13 10 13 13 13 5
14 15 5 7 14 7 13 14 6 5
14 15 15 8 13 6 7 7 5 10
[download]

Update: This is slightly slower, but appears to produce fairer results:

sub gen3 {
    my $constraints = shift;
    my @rands = map $_->{ mid } - $_->{ sd }, @$constraints;
    my @limits = map $_->{ mid } + $_->{ sd }, @$constraints;
    my $maxChange = min map $_->{ sd }, @$constraints;
    my $remainder = 100 - sum @rands;
    while( $remainder ) {
        my $target = int rand @rands;
        my $addition = 1+ int rand min( $remainder, $maxChange );
        next if $rands[ $target ] + $addition > $limits[ $target ];
        $rands[ $target ] += $addition;
        $remainder -= $addition;
    }
    return @rands;
}
[download]