In looking at the pics you posted, those two breakers are connected to what appears to be 12/3. This allows two separate circuits to share one neutral, although technically to do this, each circuit must be connected to opposite phases, since two 20A circuits on the same phase if loaded to capacity, would be putting 40A on the neutral. One 20A on each phase would only put 20A on the neutral, which is what code requires. This should not be corrected though, until you find where the two circuits are interconnected. Did you go to all the affected outlet boxes and open them up to look at the wires in them? Did any have both red and black in them?
Think about how your house is laid out. Where is your panel located? What is the first closest thing to the panel that goes off when you turn the breakers off? Judging by the age of your panel and wiring, I would say your house is probably from around the 1950s. It was common then to use a ceiling light box as a junction and split off there to feed the next device in line. I lived in a house that was built in the mid 50s, the original circuits fed things in a random way all over the house. For example, one circuit fed the garage outlet, one outlet in the family rm, the kitchen, hall and bath lights, and the outlet controlled by the switch in each of the three bedrooms. Funny enough, the outlets in the smallest bedroom were off of three different circuits. When replacing a light fixture in the master bedroom closet, I found that it was the junction point for the feed coming from the panel and from there went on to feed outlets and whatnot. I would suggest opening up ceiling and switch boxes, and to look in the junction boxes on the recessed lights. If you find that 12/3 wire, check to see if multiple wires are coming in the same clamp/knockout with it, and make sure the red and black wires in the same casing aren't accidentally hooked together at that point. If you do find that, separate the wires and turn each circuit on one at a time, and use your tester to see if that is where your problem is. At that point might be where things are supposed to split, which you can then check the remaining wires one at a time by hooking them to one of the hots from the panel and see what goes on when you turn the breaker on, and then you can decide what should go on each of the circuits. If you have a doorbell, look for a transformer mounted on a junction box and check in that to see if that is the junction point for the 12/3 wire coming from the panel. Look in what you might think would be the strangest of locations for a junction box. In that house I lived in, when the kitchen was redone, new circuits were installed for the counter outlets, and one of the original outlet boxes had been turned around to face in to the furnace rm closet, with a blank plate over it, but was still being used as a junction box to feed other things in the house.
Of course, make sure to turn the power off before opening any of the boxes. You should take the cover back off the panel again, and use your tester to confirm that the power to each of those wires coming out of the breakers is off. The breakers in those style panels have been known to sometimes fail and show that the breaker is off, when actually the internal components stay engaged and the power is still on. Not common, but better to be safe and double check.
One thing you could try first is to turn off both breakers, and disconnect the black wire. Turn the breaker with the red wire connected back on. Does everything still work off that one breaker? Then do the opposite and disconnect the red wire and turn the breaker for the black wire on. Same as before? If you do find that half of the connected devices are on one wire and the rest on the other, that could indicate a failure inside of the breaker. Those two small breakers are what is called a twin breaker, they are contained in one unit and many times share mechanical components, and the failure of one could cause incorrect operation for both, leaving you unprotected in an overload or short condition. In this case, that twin breaker would need to be replaced.
You should really try to figure out and correct this problem. Have an electrician take a look at it if you can't get to the bottom of it. At least then you can rest easy knowing that a dangerous condition has been corrected.