I don't think it is too unreasonable or that hard to train Gate Agents who work on international flights at major hubs, like ORD, to recognize what a visa looks like for a handful of international destinations. Perhaps they could show them some samples, or do a 5-minute training, or send a memo. It is not that complicated.

They are flying flights to Japan, they know that the country now requires a visa for US citizens, it is not that hard to train your gate agents.

I also assume that the OP was not the only American on that flight to TYO. How did the GA clear everyone else with a visa, and the OP with an ERFS....that should have rung alarm bells.