It... is software scaling, it's just software downscaling when most of the art assets have x2 integer scaling already applied, resulting in pixels in the sprites smaller than the 'pixels' in the background.
The way I would propose doing it is rendering the game at the same resolution as the backgrounds so that when you scale the sprites down they can't have pixels that are smaller than they should be.
Hi, I'm the writer on Primordia. You are going to make the artist's head explode. Your complaint is one that he has voiced for months and months with how the D3D visual mode works in AGS. You lose the "blockiness" of shrunken sprites that older adventure games had. For Vic -- and obviously for you -- that's a big deal. The good thing, though, is that you can fix it by changing to DDraw mode. Then the resolution will be consistent throughout (320x200 or whatever it is), meaning that the smaller sprites will turn into weird impressionistic mosaics, the way they used to. DDraw is incompatible with some newer versions of Windows, but if it works with yours, you can see the game how Victor (and the ancients) intended it to look.
For myself, I found the D3D mode to be somewhat better. The resolution issue only annoys me on rooms where the game is really zoomed out -- such as the train station interior scene that you flagged in your post. That is the worst example; there is one other room that's almost as zoomed out (though not quite as much). Otherwise, the effect is not noticeable in the vast majority of the rooms (to my eye) and in the remaining small minority it's pretty mild. The problem with the chunky DDraw mode is that while it looks better when things are way zoomed out, it looks considerably worse (again, to my eye) when the sprites are shrunken to, say, 85% or 80% or whatever. At that size, D3D doesn't appear to be in a different resolution, and the sprites have no artifacts. (For example, see http://www.youtube.com/watch?feature=player_detailpage&v=0YvWQi_5fsw#t=29s
-- the yellow robot is scaled under D3D here, but I don't think the effect is noticeable at all.)
In DDraw, the resolution looks fine, but the sprites have artifacts and look slightly messy / distorted, as was the case in classic adventure games. (Excluding Sierra games, which tended not to scale at all.) If you like the classic look no matter what, it may not bother you, but it always irked me because we use a lot of gradual scaling in rooms, so you rarely see the sprites without artifacts in DDraw.
All said, I think your eyes will adjust to the issue you're having with D3D quite quickly. Or you can play it in DDraw. In either case, though, you really do need to see how great Vic's art looks in game!