The history plugin attempts to find the transaction in its index. If it’s not in the index, it will use the block number to exhaustively search the block for the transaction. Without the block number hint, it does not try to search the entire chain.
To get all transactions into the index, replay your blockchain with the history plugin enabled. Note this will take considerably more RAM than normal, as the indexes are built in the same RAM database as chain state.