$P = IV$ and $V = IR$

As this Wikipedia article explains:

For a given amount of power, a higher voltage reduces the current and thus the resistive losses in the conductor. For example, raising the voltage by a factor of 10 reduces the current by a corresponding factor of $10$ and therefore the $I^2 R$ losses by a factor of $100$, provided the same sized conductors are used in both cases.

The key to understanding here is that the power of the high voltage line is not the heat lsoses in the wire, but the useful work done in the rest of the circuit (the load). (This useful work can be also viewed as a resistance with its own Joule's losses being the power.) Essentially, one may think of it as two resistances connected in series, of which the wire resistance is by far the smaller one: $R_{line}\ll R_{load}$. Greater load resistance leads to higher voltage, but smaller current in the circuit and consequently smaller heat losses in the wires.

In equations: $$ P_{load} = I^2 R_{load},\\ P_{loss} = I^2 R_{line},\\ V=I(R_{load} + R_{line})\approx I R_{load} $$

If the transmission lines were all DC and without any intermediary devices between generators and consumers, the sum of the currents of all consumers would be the current of the lines. Just like water supply. And the transmission line voltages would be 110 V.

But AC current makes possible the use of transformers. So, a huge voltage and a manageable current can deliver a great power in the transmission lines $(P = V_tI_t)$. Closer to the consumers, transformers lower the voltage. That way, $\sum V_cI_c = V_tI_t$, and $\sum I_c >> I_t$.

In reality, it is also possible to make the trick with DC, but not with the traditional simple transformers.

Note that the $V=IR$ (or $\tilde{V}=\tilde{I}Z$, but same concept) refers to voltage drop across the length of cable, not the voltage of the signal. If the voltage is increased and current is decreased, for example, by a step-up transformer, the power loss in the cable decreases (this is why electricity is always transmitted at high voltage). This tells us that both the voltage drop across the cable and the current through the cable have decreased.

There is more than one relevant voltage in the circuit. You need to distinguish between them.

A simple model of a power transmission system would be a wire going from generator to a 'load resistance' to which you want to supply power, and another wire running from the other end of the load resistance back to the generator.

First consider the load. Because $P = VI$, you can supply the same power to a load by using either a small voltage, $V_{load}$, across the load and a large current, or a large voltage and a small current. But, you argue, $V_{load} = IR_{load}$, so increasing $V_{load}$ must increase $I$. Wrong. What you might not have realised is that the resistance of the load is chosen to be different in the two cases. To use the same power, a higher resistance load is needed if it is to be supplied with a higher voltage. So by suitable choice of $R_{load}$ the current can actually be smaller than with a lower voltage! In practice transformers are used to make the effective load resistance what is needed.]

Now consider the transmission wires. These have fixed resistances. So the voltage, $V_{wire}$, across each wire (that is between one end of the wire and the other end) is simply proportional to the current, and the power wasted in each wire is $P=I^2R_{wire}$. So a high voltage system (one in which the load has been chosen to accept a high voltage) will take a lower current, and since it's the same current that goes through the wires, the voltage across the wires will be less, and the wasted power will be less.

I is directly proportional to V, when we assume that the circuit has a constant resistance (and variable power)

I is inversely proportional to V, when we assume that the circuit has a constant power (and variable resistance)

So, if you increase V, but keep the power constant by increasing the resistance of the circuit, current decreases.

"How is energy the same if the current decreases?"

$P=I^2R$, i.e. it depends on both the resistance and the current.

"If electrons are gaining less kinetic energy as current is less now, where is the remaining energy from the voltage source going?"

The extra energy is going to the resistance. We had to increased the resistance to keep the power constant. The now increased resistance consumes more energy. Electrons transfer their energy to this resistance.