I'm not sure what you are doing, but i get different ciphertexts for each plaintext:

#!/usr/bin/perl -w

use strict;
use Crypt::DES;

my $key = pack("H16", "hello");
my $cipher = new Crypt::DES $key;

for (my $i=1;$i<11;$i++){
    my $ciphertext = $cipher->encrypt(&pad($i));
    print "ciphertext: ".unpack("H16", $ciphertext);
    print " plaintext : ".$cipher->decrypt($ciphertext)."\n";
}

sub pad {
    my $padstr = shift;
    my $padlen = length($padstr);
    for (my $i=$padlen;$i<8;$i++) {
        $padstr = '#'.$padstr;
    }
    return $padstr;

}
[download]

Each pass produces the same ciphertext for each plaintext value:

ciphertext: b9f13b4dadafc8a7 plaintext : #######1
ciphertext: a63ce27095356ceb plaintext : #######2
ciphertext: df037bd297aa73af plaintext : #######3
ciphertext: 0eaf7e009f26dc71 plaintext : #######4
ciphertext: 878da30ec4b03db2 plaintext : #######5
ciphertext: 38bb5f88a797e62e plaintext : #######6
ciphertext: e001696d8bcec155 plaintext : #######7
ciphertext: 6c3446a5cf32e3f2 plaintext : #######8
ciphertext: 21b4798bb48eb72d plaintext : #######9
ciphertext: 8ff59b7237d31c90 plaintext : ######10
[download]

Random keys wont work unless you store the key somewhere, and associated it with the plaintext (or a hash of the plaintext), which in itself is bad security practise.

Your comment of "most of the time" I think is inaccurate. If you use the same key on the same plaintext, you will _always_ get the same ciphertext. If you didnt, then what would happen if you gave someone your ciphertext and the key, and asked them to decrypt it? - it would produce the incorrect result.

Check out Applied Cryptography. Its a fantastic book that explains symmetric (DES) and asymmetric (RSA) algorithms (among other things)..

Are you able to explain the wider problem, or post a code snippit?