Hmm.
Hmmmmmm.
Interesting stuff. It could play one of several ways, depending. I'm not entirely sure, especially since I don't know much of your players, if there's even an actual problem, per se.
One thing I will say: don't try to 'fix the players' or otherwise force them to the path of righteousness by some hamhanded story tactic. It generally tends to backfire, if you spring it on the players with no warning. Resentment can even be a result, over time.
First thought: this is a steampunk universe. Generally, this impies a different moral subset than standard fantasy. This may be an issue. Further, the old saying is "A cornered animal is the most dangerous one of all." You've pushed the PCs up against a wall, possibly showing them that the normal authorities are corrupt or of no help and then sent them packing. They may think they have to be SOBs, because that's the only way to survive, and everyone is a potential enemy, stooge or snitch.
Second thought: the unreality of the 'bouyancy' wizards, and the schlock nature of them may have corrupted the tone you were shooting for. Yes, they may have become creepy later...but that time, you may have pushed your players into 'GURPS Goblins' territory, instead of 'Diamond Age' or 'Castle Falkenstein' territory. They may have assumed that they had wandered into a world with a different subset of rules and mores, and subsequent behavior flows from that. Maybe they even view everything as sort of a black comedy, or that being an anti-hero is actually what you wanted.
Now, the situation is hardly irreversible, I would expect. Heroes on the mend is a popular concept, and certainly nothing you can't work with. Here's a few ideas for you:
1) Discuss this with your players. Don't just say "I don't like it.", but say "how do you feel about the way the game is going?" Find out what they expect, what they expected going in, and if there's a disconnect going on. You don't have to say "I need to change this or the game is over." (though you could), but perhaps "I'm not sure I like where we're heading, and not sure that we can run a campaign of any length like this."
2) Read Kid Charlemagne's suggestion. It's a really good one. It puts the situation in the player's faces, but it isn't railroading and gives them the power to address the situation. Unlike the 'uber-NPC' schools you, it generally gives the players both an RPG opportunity without making them feel like you're hitting them with a hammer.
3) Have the bad guy send some emissaries to the PCs. Have them offer to recruit them. That's right, have their enemy offer to hire them...because he didn't realize they were such bastards. Either way, you have some good opportunities: if they say no, they've got something to chew on...in fact, you could make it the start to an adventure, as they trail the guy or something similar. If they say yes, you can try to steer it to a 'good guys working undercover or trying to reform a bad organization'. Angel's fifth season showed how this could be an interesting and workable premise.
4) Have word spread of them to other villages and towns....but don't make them send for a brigade of paladins: make them terrified. Truly terrified. Have NPCs scream and run to their homes when they see them coming. Think of viking raiders setting upon a hapless and undefended farming village. The blacksmith can't forge horseshoes for their animals, from shaking so much for fear that they'll kill him and harm his daughter. Imagine a set of terrified commoner/expert 1s armed with farm implements making a stand while the women and children flee to the hills. They don't attack, just try to stand in-between the PCs and the escaping families....and the PCs just standing, dumb-founded. "But...but...we're don't even have our weapons out. We're not here to hurt you! We just need some supplies!"
Now, if PCs feel empowered, rather than horrified by this, you have a few choices to make.
1) have the bad guys notice them, and consider them competition...competition that needs eliminating. Soon they find themselves in the midst of a war between BBEGs, perhaps.
2) Make it clear that you're not interested in running a game where the PCs behave like sociopaths on a 'natural-born killers' style rampage. Either they choose to start acting like heroes, or perhaps a new game is in order...because you don't like creating adventures in that light.
3) Have the good guys offer them a deal to 'get out of jail'. Essentially, if they behave and prove themselves, they can be exonerated...but if they choose not to, they WILL be hunted, and they will fall. One Greater Planar Ally later, and the eclisiarch of the local church will have more donations from the faithful, and the PCs will be dead.