Given that being out of power for so long would get enough people to start thinking that they're unelectable you'd get people wanting to start frest basically. Hell you'd see people saying the next time they do win back the White House that it was a fluke which if they don't win reelection would really drive that home.
They didn't IOTL, take a look at their Civil War to pre-FDR record. America only allows herself two political parties, losing 4 Presidential elections in a row isn't going to change that.
I've always thought that Powell would've run in 96 if it wasn't for the fact he would've been going against a popular(well popular enough to insure that victory would've been fairly hard) incumbent. 96 with Bush having won reelection IMO means he runs meaning that the GOP would probably win in 96 and maybe even get Powell reelected in 00. Which if that happens might spell the end for the Democratic party as we know it.
Colin Powell could not make it through the Republican primaries in 1996, barring incredibly unlikely events occurring. He would certainly stand a good to really good chance of winning against Clinton or whoever and becoming President, no question, but the primaries are basically insurmountable.
The best chance for Bush would have been Perot staying out of the race.
The various political science papers I've read on the subject are in unusual agreement that Perot basically split votes equally between the two and would not, surprisingly, have changed the outcome. However if you wanna talk about the impact on the campaign and news media that he had by entering, that is certainly a broader and less settled question.
One thing is for certain. The GOP would not retake congress in 1994. They took control OTL largely because of the Assault weapons ban (the nra put a ton of money into Republican congressional campaigns), and Clinton's failed attempt of Health care reform. With Bush in the White House, none of that happens, nor does the Omnibus Budget Reconciliation Act of 1993 (unfortunately) so that along with the fact that the president's party almost always loses in congress gives the Democrats another 4 years.
Eh. Depends. IOTL 1994 was the end of the line for Southern Democrats, plus Newt and friends was smart enough to bring MARS (Perot) voters--who were very liberal on spending and anti-NAFTA and anti-corporate, but against helping poor and black people and disliked Washington folk--into the party. Is Newt still smart enough to pull that off with Bush in the White House? Well, no, probably not but 1992-96 was a major realignment in American politics that Bush keeping the White House may not change too much.