A couple of observations from number theory to reduce the search space. The number 2003 is congruent to 5 mod 9, and taking sums of base-ten digits reduces them mod 9. If three permutations of digits $x, $y, and $z could solve the puzzle, then:

(3*($x+$y+$z) % 9) == 5
[download]

But 3 has no inverse mod 9 because of the common factor, so it's impossible with 3 permutations.

if (4*($x+$y+$z) % 9) == 5  then ($x+$y+$z) % 9 = 8
if (5*($x+$y+$z) % 9) == 5  then  ($x+$y+$z) % 9 = 1
if (7*($x+$y+$z) % 9) == 5  then  ($x+$y+$z) % 9 = 2
[download]

6 is impossible because of the common factor. For any given $x, $y you can calculate what $z would have to be (or eliminate it if it's a duplicate of the others). That should cut down your search space by a lot.