#!/usr/bin/perl
use strict;
use warnings;

my @digits= qw(9 8 7 6 5 4 3 2 1);
my $max= 0;

permut('', @digits);
print "Solution: $max\n";

sub permut {
    my ($s, @digits)= @_;
    my $i= scalar @digits;
    DIV: {
        { no warnings;
            last DIV if $s<$max;
        }
        foreach my $i (split //m,$s) {
            last DIV if $s % $i;
        }
        print "$s\n";
        $max=$s;
    }
    if ($i) {
        while ($i--) {
            my $f= shift @digits;
            permut($s.$f, @digits);
            push(@digits, $f);
        }
    }
}
[download]

My solution and the time needed on a 900MHz Power PC G3 with 640MB and lot's of Java running in the background ;-) is:

9867312
real 2m14.144s
user 0m32.100s
sys 0m0.730s