What I don't get is - the power passing over any given circuit is I*V. So, the same amps (I) and higher voltage (V) would cause more energy to be passing through the fuse and, subsequently, should create more loss in the same resistance, more heat and have it melting faster. Yet apparently it does not matter.
Correct. Only current counts. For fuses, the more useful form of the elementary power equation is P = I**2 * R. The resistance of a fuse is very low in comparison to the resistance of other devices in the circuit, so very little of the voltage drop happens across the fuse. However, the current working in the material generates heat in proportion to the square of the current, and fuses are made of a material that melts at a low temperature. If the current is too high, the material melts and the fuse blows.