I'll offer a response broken into 2 sections:
- Was Paul a Jew?
- If yes, what kind of Jew?
1. Was Paul a Jew?
There is a risk here of imposing anachronisms on Paul: we are accustomed to thinking of Judaism & Christianity as separate and distinct entities; this was not the case during Paul's lifetime.
To Paul and his contemporaries, one could be both a Jew and a Christian and there was no inherent contradiction (for example, see Acts 18:2 in which Aquila, a Christian, is referred to as a Jew). The full separation of Judaism & Christianity into distinct religions did not happen until the Flavian era (70s-90s), and was closely tied to the destruction of Jerusalem (source).
Paul makes it very clear that he is a Jew:
Circumcised the eighth day, of the stock of Israel, of the tribe of Benjamin, an Hebrew of the Hebrews; as touching the law, a Pharisee (Philippians 3:5)
(note that verse 7 does not say he gave up these parts of his identity, but that he gave up some advantages these attributes might otherwise have given him)
Although there was substantial effort in 19th & early 20th century German scholarship to argue that Jesus and those close to Him were not Jews, this was more a political move than anything else. Jesus, Peter, Paul, and almost every major character in the New Testament were Jews. They were born Jews, they received a Jewish education (to varying degrees), their teachings are culturally Jewish, and they relied heavily upon the Jewish scriptures.
Yes, Paul was a Jew.
2. What kind of Jew?
Josephus records that there were 4 principal sects/philosophies of Judaism in the late 2nd-temple era:
(These could certainly be sub-categorized further. For Josephus references, see e.g. Antiquities 18.1.1-6).
Paul certainly was not a Sadducee, Essene, or Zealot. The Pharisaic views of the 1st century were not monolithic--plenty of in-house debate there--but I will make the case below that Paul had no reason to stop identifying as a Pharisee. As noted in the OP and other answers, some Pharisees accepted Jesus as the Messiah, but many (leaders in particular) did not.
Paul's claim in Philippians "as touching the law, a Pharisee" can be read to mean that he identifies as a Pharisee and/or he was educated as a Pharisee (like someone today may claim to be a X_University-ite not because they currently attend, but because they received an education there); it does not mean that he accepts all statements made by the leaders of the Pharisees.
Perjury is a bad strategy
Paul is on trial (Acts 22:30) and his prosecutors are out for blood (Acts 22:22). If he makes a statement that can be falsified, he can be charged under both Jewish (Leviticus 19:11) & Roman law (Paul on Trial p.156).
By highlighting a difference in the theological views among his accusers (Pharisees & Sadducees) he gives himself a way out...but also goes on record in a court of law--a record to which his accusers will have access (ibid p. 156) when they try to impeach/discredit his testimony later (Acts 24:1-2).
Now that Paul is on record declaring himself a Pharisee, if there's a viable means of showing that testimony to be false, Tertullus can show Paul to have perjured himself when he accuses Paul in Acts 24 (see vss. 5,6,9)
Matters of in-house debate among Pharisees won't be too helpful to Tertullus et al here (e.g. varying levels of rigidity in interpreting the law), but the salient differences among the Jewish sects would. Luke calls out the most relevant differences in verse 8: the afterlife & non-mortal beings.
Paul's teachings are well-known and widespread (see Acts 24:5); if he's been preaching something that is a clear departure from Pharisaic views on the contested matter of the afterlife, the Sanhedrin can paint him into a corner. "I am a Pharisee, the son of a Pharisee: of the hope and resurrection of the dead I am called in question" (verse 6) is a very risky thing to say in front of the authorities on Pharisaic doctrine. To get away with this (no accusations against Paul on this matter are raised before the Sanhedrin or in the appeal before Felix), Paul's Pharisaic credentials must be as impeccable as he himself suggests when writing to the Philippians a few years later (see above).
Paul's letters support his testimony of his Pharisaic credentials. He regularly quotes from the Writings & the Prophets. Origen of Alexandria reported that:
the Samaritans and Sadducees...receive the books of Moses alone (Contra Celsum 1.49)
Others suggest that perhaps the Sadducees held the Torah in a place of greater honor not afforded to the Writings & the Prophets, but still used most/all of them. Either way, Paul's extensive usage of the Tanakh (not just limiting himself to the Torah) suggests a Pharisaic leaning well after his conversion to Christ.
Indeed, Paul's method was to start proselyting in a city by going to the synagogue and teaching the message of the Messiah from the Jewish scriptures (see Acts 17:1-2, 18:4-6). Paul saw Jesus as the fulfilment of Old Testament promises, not the destruction of them.
There is no statement from him or his enemies suggesting that belief ever changed or engendered conflict.
Under Roman Law, Judaism had the significant distinction of "religio licita" (legal religion), a privilege granted only to the Jews & its own (Roman) Pantheon of gods (Paul on Trial p.13). In order for Christianity to receive these legal benefits it was necessary to present it as part of Judaism (or as the true Judaism), not a separation from it.
The litigation strategy of Paul's accusers was to charge that he was creating an illegal religion thereby disrupting society. Although Christianity had a persuasive claim to legality as a sect of Judaism, it was caught in the cross-currents between Jerusalem and Rome. In the midst of this legal/political/religious cauldron, Acts was written (ibid pp. 13-14).
If Paul has taught (or can credibly be accused of teaching) a view of the spiritual realm foreign to all major sects of contemporary Judaism, Paul (and Luke) have no religio licita leg to stand on.
Paul was familiar with the teachings of the Pharisees--if there were points of disagreement between him and them, they would have featured regularly in settings such as Acts 19:8-10. Paul's letters give us a pretty good idea what the controversies were in the churches he wrote to, and disputes of Pharisaic teachings do not feature prominently at all.
If Paul's history as a Pharisee led to doubts about his sincerity as a Christian, Paul's failure to guard against this, combined with statements like those found in Philippians 3:5-7 & Galatians 2:2-15, would be absurd.
- Paul was the son of a Pharisee
- Paul studied under Gamaliel
- Paul presents himself as a Pharisee while on trial before the Sanhedrin (Acts 23)
- Paul presents himself as a Pharisee when writing to the Philippians (Phil. 3) -- not a brilliant move if this is a claim that already got him into trouble in Jerusalem and/or Caesarea
- Conclusion: the written record supports the claim that Paul never stopped being a Pharisee.
Paul's enemies wanted him dead, and catching him in perjured testimony before the Sanhedrin would have been devastating to Paul's case. I suggest that the inference to the best explanation is that Paul's enemies didn't use this tactic because there was no evidence of perjury: Paul's claim to be a Pharisee was incontrovertible.
Yes, Paul still really was a Pharisee. He was also a Christian; during his lifetime these were not mutually exclusive. In claiming this, Paul would not be expected to agree with all of the teachings of the leaders of the Pharisees any more than they were expected to agree with each other.
If he wasn't a Pharisee, he has nothing to gain by claiming--during a trial--that he is. If Paul's identity as a Pharisee were a point of controversy, we should reasonably expect this to come up in his letters, especially in his letter to the Romans wherein he introduces himself to this audience and corrects against misleading statements they've heard about him.
Paul's letters are "occasional" documents--they were written to respond to specific controversies and questions, not to preach Christian theology from the ground up (he may at times appear less Jewish here when he's speaking to Gentiles and applying the method he describes in 1 Cor. 9). Paul's Pharisaic credentials do not appear to have been one of these controversies that needed to be addressed.