Pacts with dieties, dragons, celestials, elementals, Far Realms critters, totem animals, place spirits or vestiges also seem like possibilities.
Vestiges, in particular, could evoke an Houngan-style Warlock, who calls some sort of spiritual presence into himself to fuel his warlock abilities, and calls up another spirit within himself to invoke a different ability.
Most of this could be handled with light or no mechanical changes, merely flavor text. I played a Daelkyr Half-blood Warlock who had a very Far Realms feel to his invocations with no mechanical changes at all. His Summoned Swarms looked like alien critters (spinning floating starfish-looking critters instead of bats, for instance), but used the same rules.