how to rewire 3 way switch
Several wires in a sheath is called a cable.  The difference gets important fast. 

Traveler wires

First, it's time to stop the dizziness and confusion with the travelers.  You should not have to play musical chairs with travelers.  (It's not hazardous so as long as you are only exchanging the wires which belong on the 3-way, but it's a stupid waste of time).  And to save us trouble later, let's mark the travelers; I recommend yellow tape, but if that color is already assigned, just use blue.  Mark both travelers the same color, there is no need to distinguish them from each other.  

This will always be true about travelers: 


There is no wire-color standard. Really. That's why we mark them! 
Both traveler wires are in the same /3 cable 
Both traveler wires go to the 3-way switch
In the same /3 cable, travelers stay the same color. We don't have "crossover cables" in mains electrical. 
However if the /3 cable is spliced somewhere, all bets are off. 


So. In box 2, all 3 wires go to the switch, so that's no help at all.  However in box 1's left /3 cable, red and white go to the switch.  Gotcha! 

Red and white get marked yellow (or blue if you prefer).  In switch #1 box, and also switch #2 box, unless you have reason to believe the cable is spliced somewhere else.  

Identifying the common screw terminal

You've talked a lot about screw positions and never about screw colors.  On 3-ways, screw positions are meaningless. Screw colors matter.  The common screw is black, the traveler screws are brass/yellow. 

Now we've identified the traveler positions by logic, and identified the traveler screws by color.  There is only one way this can possibly connect, and it must work. Unless: 

A third 3-way (4-way), or splice in a lamp box?

Remember the part where I said "if the /3 cable is spliced in another box, all bets are off"?   That could happen in a lamp box, or the site of a current or former 4-way switch. There's no substitute but to search every possible box for this.  You'll recognize it when 2 wires from a /3 cable are spliced to 2 wires from another /3 cable. (Not counting grounds). 

In that case, the traveler principles still apply, but you have to figure out which cable is which amongst several white /3 cables coming into that intermediate box.  ...and this, this is why I advocate marking travelers with colored tape. 

There's one more possibility.  Here, we presume the left /3 cable connects to box 2.  What if it's actually the right /3 cable??? That would make this whole thing a bodge job of considerable proportion, but it would explain a lot. The troubleshooting here might be beyond you, and it might be time to bring in a handyman.