Was Redcloak evil since the beginning?

[Peelee]

As divinely ordained characters, paladins receive their powers from a god.

Nope. Paladins did not require any deity whatsoever. Miko and the rest of the Sapphire Guard may have hitched their wagons to their deities, but Azurites were already largely depicted as hyper-religious anyway, so this isn't really surprising. But nothing has indicated any of the other paladins we have seen have had any sort of connection to a deity, and their powers do not come from deities any more than a druid's or a ranger's.

Paladins were the exception to the system, however - they explicitly can't game the system: knowingly perform a chaotic action and you lose your paladin abilities until you atone.

In addition to being incorrect on how paladins in OotS work, you are also incorrect on how paladins in standard 3.5 D&D work as well.