The problem was resolved by changing the water pump casing and gaskets.
The pump case was eroding away in flakes. Holes in the lower pump case and gaskets diverted part of the water flow into the lower unit (where the weeping holes are). Once enough water had filled up in the casing around the pump, the pump could prime. Only then could the water flow up into the engine normally. It may explain why the problem was intermittent.
Lower pump case with corrosion holes. Salt had eaten through it.
[High Res]
The lower gasket (against the lower unit's drive bearing) and casing were completely kaputt, crystallized in salt and rust, corroded through. The upper pump parts, and the impeller appeared to still be healthy. Most of the parts are included in the tohatsu pump kit, including a new impeller, but the lower pump case had to be purchased separately.
I'm not sure why the casing has to be made of this particular metal -- it seems a thermal plastic would fare much better. The bolts, metal gaskets, and plastic pump covers were like new, once cleaned. The revised impellers for that engine now have a plastic inner band instead of a metal one, because apparently the metal ones were prone to seizing.
The upper parts were still in decent shape [Full Res]
It's a relatively straightforward repair, but here are a few lessons learned:
Read the manual. Learn the correct way to transport and store your outboard. Accidentally laying the engine down on the wrong side, or with the propeller higher than the motor may spill oil everywhere. Something the manual doesn't tell you is that it may also lock the pistons. Hydraulic lock means you can't turn/crank your motor because pistons are filled with oil -- This situation is easily solved by pulling the spark plugs and pulling the cord (or using the electric starter) while plugs are out. The engine won't start without the plugs, but the pistons will be be flushed out via the plug holes. Look it up.
Read the manual. Rinsing the salt water out of the engine after each use extends the life of the parts. Hard learned. Tohatsu sells a very inconvenient garden hose screw attachment. You have to remove the water screw from the lower unit, and cover the intake holes with tape. If your boat stays on the water, a much more convenient option is to get one of those engine flusher "earmuff" cups which can slide the hose over the water intake on each side. You don't have to unscrew anything, and you can even do it while the engine is in the water.
This was not covered in the user's manual: The water flow into the engine is also controlled by a thermostat. If you find your pump is severely corroded, you should also check your thermostat because it will most likely also be corroded. The thermostat can't get a reliable reading when it's all salted up. It's easily accessible under the cowl. The thermostat cover is attached by two bolts. You can wiggle the thermostat out, inspect the thermostat and its socket, and clean everything with fresh water.
I couldn't find the torque specifications for any bolt in the pump, lower unit, or thermostat cover. I'm not sure it's critical. I used my best judgement -- more than finger tight, but not enough to crack/strip plastic parts.
Taking the lower unit out: The most frustrating step of the repair is disconnecting the shifter linkage arm -- it is held by two rollpins. You only have to undo the lower rollpin from the shifter linkage arm, the upper one can stay. The other outboard brands commonly connect the shifter linkage to the lower units using two nuts. Tohatsu uses 3mm rollpins (aka springpin) instead, which take some work to remove. It is best done by leaning the engine on its side, and then wedging a piece of wood behind the arm to counteract the pressure (of punching the pin out). To push the pin out, you can file a nail to the right size (3mm diameter), or get a 3mm roll pin punch/remover (~$10). In a pinch, a 3/32 punch will do, but you'll likely mushroom the pin. You can also get the official tohatsu roll pin remover which is more expensive -- ~$50. The length of the official rollpin is 10mm.