I think I found a workaround for this issue (and found some other bugs while doing it - but at least it puts this behind me).
First I discovered that it affects only the command line, the applets work fine, as reported by
http://www.javatester.org/version.html.
I had been changing the preferred version of Java using "Java Preferences" and while the changes seem to take effect for applets, it didn't change the behavior of the command line java.
So I did a "which java". Then I followed the symlinks with "ls -l" all the way to the actual file.
It seems that we have several versions of Java under /System/Library/Frameworks/JavaVM.framework/Versions, and the current version, as seen by the system, is dictated by /System/Library/Frameworks/JavaVM.framework/Versions/Current. Now this was pointing to the folder "A". That didn't seem right (not a recognizable version number). All I had to do was to re-link to a valid version like so:
cd /System/Library/Frameworks/JavaVM.framework/Versions
sudo mv Current Current_old
sudo ln -s 1.5 Current
and now Java works ! (you could pick other versions than 1.5, I tried 1.4.2 and that works too)
So there are 2 issues open for Apple:
1. what's up with that "A" version ? - it seems to be different than all others which sound legit (e.g. the size of java executable differs) and why's that the default "current" version
2. why changing the preferred version through "Java Preferences" has no effect ? - it launches the same executable image (perhaps it should do the relinking I had to do manually as explained above)
All in all, java seems to be working now, after all these contortions.