in reply to
The Unicode Bug with Transliteration or Substitution
Regarding the different behavior of some machines (given that they all have Perl 5.8.3), I'm sorry that I don't have explicit details that would be relevant, but looking over some email from 2004 just now, I noticed that Dan Kogai was releasing updates to the Encode module independently of perl releases. I know there were some subtle but notable bugs in earlier Encode releases.
I wonder if your various systems with 5.8.3 might have different versions of Encode.