The only story with an unlikeable protagnist whisked away to alien planet and a fantasy flair that comes to mind is Heinlein's Glory RoadGlory Road. I haven't read it in decades so I can't attest to winged troublemakers.
EDIT For For some reason this also putreminded me in mind of Michael Moorcock's Sojan the SwordsmanSojan the Swordsman, which in turn led to this double novel...might It might be worth a gander