Why are my three-way switches behaving differently than they were?
This kind of switch does not have "ON" and "OFF" positions, just "UP" and "DOWN". 

There are two and only two ways to set up the action of a circuit with two "two-way" switches: 

(1) ON when switches are in different positions
UP + UP = OFF
UP + DOWN = ON
DOWN + UP = ON
DOWN + DOWN = OFF

(2) ON when switches are in same position
UP + UP = ON
UP + DOWN = OFF
DOWN + UP = OFF
DOWN + DOWN = ON


I have no confidence at all that you correctly remember which way your switches worked before your power failure incident. This kind of switch is entirely mechanical with no electronic parts and cannot suddenly change its behavior in the way you imply. 

Apparently from your second and fourth paragraphs, on three of your circuits, you currently have (1) but you want (2). 

The standard way to switch between actions (1) and (2) is to pull out one of the switches and swap the travelers, which are the wires on the two terminals that are not marked "common". 

In your case, however, I note that your switches are wired using the backstab terminals, which makes it hard to remove the wires without damaging something. So I recommend this method: in each circuit you want to change, unscrew one switch, don't change any wires, rotate it one half turn, and screw it back in. Replace the cover plates.