To add to the other answers, there is a wealth of textual evidence suggesting that at least some tribal identification remained in the timeframe between the Seleucids and the Romans and beyond.
For example, R. Yochanan bar Nafha, who lived 100 years after the destruction of the 2nd Temple, identifies himself as a descendant of the tribe of Joseph. From Talmud Bavli, Bava Metzia 84a:
The Rabbis said to Rabbi Yoḥanan: Isn’t the Master worried about being
harmed by the evil eye by displaying yourself in this manner? Rabbi
Yoḥanan said to them: I come from the offspring of Joseph, over whom
the evil eye does not have dominion, as it is written: “Joseph is a
fruitful vine, a fruitful vine by a fountain [alei ayin]” (Genesis
49:22); and Rabbi Abbahu says: Do not read the verse as saying: “By a
fountain [alei ayin]”; rather, read it as: Those who rise above the
evil eye [olei ayin]. Joseph’s descendants are not susceptible to the
influence of the evil eye.
This suggests that at least some tribal identification was acknowledged even circa 200CE. And from the text, it appears his tribal identification was not considered an unusual or outlandish claim.
Less convincingly, but still worth noting: the Jewish Virtual Library gives additional Jewish and Christian sources attesting existence of tribal identification, often referring to them as a matter of fact. Many of these sources were written between 200BCE and 200CE, and one of these sources (Tobit) was found among the Dead Sea Scrolls community:
The belief in the continued existence of the ten tribes was regarded
as an incontrovertible fact during the whole period of the Second
Temple and of the Talmud.
Tobit, the hero of the apocryphal book of
his name, was depicted as a member of the tribe of Naphtali;
The Testament of the 12 Patriarchs takes their existence as a fact; and in
his fifth vision, IV Ezra (13:34–45) saw a "peaceable multitude… these
are the ten tribes which were carried away prisoners out of their own
Josephus (Ant., 11:133) states as a fact "the ten tribes are
beyond the Euphrates till now, and are an immense multitude and not to
be estimated in numbers."
Paul (Acts 26:6) protests to Agrippa that he
is accused "For the hope in the promise [of resurrection] made by God to our Fathers. It is the promise that our twelve tribes hope to attain, as they earnestly worship night and day...Why is it judged incredible by any of you that God raises the dead?,"
James addresses his epistle to "the twelve tribes which are
scattered abroad" (1:1).
The only opposing voice to this otherwise
universal view is found in the Mishnah. R. Eliezer expresses his view
that they will eventually return and "after darkness is fallen upon
the ten tribes light shall thereafter dwell upon them," but R. Akiva
expresses his emphatic view that "the ten tribes shall not return
again" (Sanh. 10:3). In consonance with this view, though it is agreed
that Leviticus 26:38 applies to the ten tribes, where R. Meir
maintains that it merely refers to their exile, Akiva states that it
refers to their complete disappearance (Sifra, Be-Ḥukkotai, 8:1).
And, of course as you mention in your post, Paul the Apostle identifies himself as a Benjaminite in his letter to the Romans, dated 50-60 CE:
I say then, God has not rejected His people, has He? May it never
be! For I too am an Israelite, of the seed of Abraham, of the tribe of
Benjamin. God has not rejected His people whom He knew beforehand.