Why not deputize one FA on every flight to randomly search pax after they've boarded? @:-)

While providing much-needed extra income to the designated FA (a useful federal subsidy of sorts to the airlines), it would be much more efficient than the pre-boarding search, i.e. "Let me help you get that bag into the overhead, Sir, once I've finished rummaging through it."

Many domestic FAs are already well qualified to identify suspicious behavior, such as pax in F who ask for pre-departure beverages or who want their coats hung up, or especially UA flyers who ask if Ch 9 will be on.