Wrestlemania XV
Austin vs The Rock vs Mankind - WWF Championship
According to Foley's book, this was the original plan for WMXV. Which made sense, since the three had been feuding for the belt six months prior to the event. However, Foley was eventually removed from the equation, and the match was made a singles match for the WWF Title. Shawn Michaels apparently told Vince that a WWF title match should always be a one on one match, and a triple threat would go against the tradition (though he was pushing for The Rock to be out, not Mick Foley, which I'm sure The Rock is still pissed about). Moreover, Foley was in terrible shape in the weeks prior to the event. The deciding factor was that The Rock vs Austin would be a bigger draw than Austin vs Foley. Mankind was put in an extremely short match against Big Show (again possibly because of Foley's shape), and Austin vs The Rock turned out to be a pretty good main event. Foley recently revealed that he cried once he realized he wouldn't be main eventing WM that year...
Ken Shamrock vs Val Venis vs Billy Gunn vs Goldust - Intercontinental championship
Road Dogg vs Al Snow vs Bob "Hardcore" Holly - Hardcore Championship
This was the original plan for the Wrestlemania XV IC and Hardcore title matches. Both groups of people had been feuding for 3-4 months for their respective title. However, two weeks before WM15, Road Dogg was booked to win the IC title against Val Venis on RAW. Billy Gunn won the Hardcore title from Hardcore Holy the same night. Billy Gunn would go on to defend the Hardcore belt at WM (in a losing effort) against Al Snow and Holly, and Dogg would successfully defend the IC belt against Ken Shamrock, Goldust and Val Venis (though he would lose it the belt 24 hours later against Goldust, who would lose the title to Godfather two weeks later...). The reasoning behind this is Russo wanted to shock things up...He basically sacrificed the integrity of both feuds for ratings...
Butterbean vs Dr. Death Steve Williams
I can't confirm that this one was actually in the works. However, I believe this match may have occurred under normal circumstances. The purpose of the Brawl for All tournament was to push Dr Death Steve Williams as the toughest guy in the WWF. Everyone within the organization expected him to win. However, Bart Gunn inexplicably defeated him, and ended up winning the tournament. Not only was the purpose of the tournament annihilated, but the entire thing was received with disdain by wrestling fans. Moreover, several superstars were put on the injury list (including Godfather, who was out for three months). Brawl for All would somehow continue at WM XV, as Bart faced Butterbean, and get annihilated in less than a minute, thus concluding one of the worst flops in WWF history.... It's possible that Steve Williams was to take his place had he won the tournament. I'm somewhat of a conspiracy theorist when it comes to the wrestling, and I like to think that JR convinced Gunn to face Butterbean since he knew the latter would kick his butt. Which would make sense, considering Steve Williams was one of his boys...
Triple H vs Steve Austin - WWF Championship
HBK lobbied very hard for his friend Triple H to win the Survivor Series 1998 Deadly Games Tournament. He was to join the Corporation as the new world champion, and feud with Austin for the next several months. Austin would challenge Triple H for the championship at main event of WM15. However, Triple H had to take some time off after Summerslam of the same year, and with the rehab taking longer than he was expecting, he was unable to participate in the tournament. Rock was given his spot.
Mark Henry & D'Lo Brown vs Jeff Jarrett & Owen Hart - WWF Tag Team Championship
The plan was for both team to have a rematch of their Saint Valentine's Massacre encounter. Problem is, Mark Henry was injured shortly before the February PPV, and as such Henry had to be written off TV (JJ destroyed a guitar on Henry's knee). Henry was still expected to return shortly before WM. But his rehab took another 6 weeks (he returned on the pilot episode of Smackdown). Test was picked as his replacement at the very last minute (quite literally, as D'Lo and Test won a battle royal minutes before the show started)
Wrestlemania XVI
Steve Austin vs Big Show
The Rock vs Triple H
The Rock vs Triple H vs Big Show vs Chris Jericho: WWF Championship
When Big Show jumped ship to WWF in 1999, one of the stipulations in his contract stated that he was obligated to get a Wrestlemania main event match for the WWF title. The early plan was for him to face Steve Austin at WM16. Problems arose when Austin's growing neck issues eventually caught up with him and was unable to wrestle for nearly a full year to have surgery + rehab. Moreover, Show was nowhere near ready to main event WM.
Originally, Rock and HHH were supposed to settle their feud in some sort of gimmick match. Vince and the creative team still had to deal with the problem of the stipulation in Big Show's contract. So he was added into the mix, and the match became a triple threat for the WWF title. However, it was felt that it needed another big face to make it a Fatal Four way match. Chris Jericho was strongly considered. there was concern about Jericho's lack of drawing power, though. As such, Y2J didn't get to main event WM that year. Mick Foley, whose popularity was red hot following the retirement angle at No Way Out 2000, was asked to come back at WM for one final match (yeah right...). The match also added another stipulation that there would be a member of the McMahon family for each competitor.
X Pac vs Kane
According to Sean Waltman, he had an idea to extend the feud between X Pac and Kane all the way up to Wrestlemania. The idea was to finish the feud in a Barbed Wire Cage Match, with explosives. Didn't happen for a couple of reasons: One, the tech team couldn't get the explosives to work in such an cage. Second: X Pac had a fractured hand, and had to wrestle with limited capacity (Hence the reason why he ended up in a tag team mach with Rikishi as Kane's partner, and Road Dogg as X Pac's partner).
Steve Austin vs The Rock
One of the plans for WMXVI was for the Rock and Austin to go at it for a second round., with Austin possibly turning heel. With Austin out due to injury, the match had to be delayed a full year. Timing worked fine for the company, as WMXVI still managed to make a huge draw.
Wrestlemania XVII
Steve Austin vs The Rock vs Triple H - WWF Title
The early idea was for Triple H, Stone Cold and the Rock to go at it at the biggest stage of them all (which would have been the first time the three men would go at it on PPV, as their planned Survivor Series match never occurred because of Austin's need for neck surgery). Triple H felt (just like his friend Shawn Michaels) that triple threats for the WWF Championship at Wrestlemania would be breaking the tradition. He opted out of the title match. Rock vs Stone Cold II for the belt was then decided to be the main event..
Triple H vs Shawn Michaels
HBK was heavily rumored to make his return at WM17, for at least one more match. During his last TV appearance in 2000 (in which he explained Mick Foley his whereabouts during Survivor Series of the previous year, during the Who Ran Over Austin angle), he looked in great shape. Moreover, he told the crowd "Four Months". Everyone assumed that he would return some time before WM. And there was actual plans for HBK for WM17. First, he was to face his best friend Triple H. However, it was later decided to use as a non-wrestling role (Triple H's manager?), in order to set a feud between the two. Shortly before WM, he showed up at work higher than he's ever been, and was basically told to go home. HBK's return was delayed for over a year, after he finally confronted his demons and took back control of his life.
Triple H vs Hulk Hogan
Another idea was for HHH to face Hogan. The latter had no contractual obligations to WCW and was a free agent. Vince tried to have him sign a contact for WWF, but they couldn't reach a deal. Hogan would reach a deal (Along with Nash and Hall) a year later. HHH was once again without an opponent.
Triple H vs Ray Lewis
Triple H vs Mike Tyson
WWE.com mentions this one as well. Vince was pushing for Triple H to work with a celebrity as as throwback to Wrestlemania 11.. Several names were thrown in the hat: From Superbowl champion Ray Lewis to a "big Japanese guy who was the Pride Champion, according to Triple H". Eventually, Mike Tyson was selected. (Which would make sense, considering the history between the two at that point). The plan was to have a six round boxer vs wrestler match, with both Earl Hebner and Millis Lane. However, Tyson demanded an astronomical amount of money. Match didn't take place.
HHH was yet again without an opponent. Taker was rumored to join forces with Kane to face Rikishi & Haku at Wrestlemania, but didn't happen. Both Taker and HHH being free for WM, the two having a match was a natural thing.
Mick Foley vs Vince McMahon
In the last weeks of 2000 Vince McMahon was feuding with Mick Foley. Vince was accusing then commissioner Foley of being irresponsible and putting the WWF Superstars in jeopardy. Eventually, Mick was fired (Mick Foley fired on national TV? Certainly you jest!). William Regal replaced him as commissioner. It was safe at that point to expect Foley to have a match with either Regal or McMahon. Foley said he wouldn't wrestle Regal at Mania. The reason was, as much as he respected Regal, he's not the kind of guy he'd come out out retirement for and have one last great match with. He also said no to a fight with Vince, since he didn't think he'd ever wrestle again. He agreed on being referee in the Shane/Vince match. The relationship between Foley and McMahon has never been the same since.
Wrestlemania XVIII
Triple H vs Steve Austin - Undisputed Championship
The Rock vs Steve Austin
Hulk Hogan vs Steve Austin
Chris Benoit vs Steve Austin
Kurt Angle vs Steve Austin
This is perhaps the craziest WM in terms of the number of plans this one went through.
The plan was for Austin to win the Undisputed title at Vengeance 2001, and defend the title against his former tag team partner, Triple H. Austin was to go to WM as the heel, while Triple H would benefit from a babyface turn from his return. HHH would win the Rumble, and challenge Austin for the belt. However, this was shelved once it was deemed Austin would be a better fit as a face after the InVasion storyline concluded, and Jericho was the one booked to win the Undisputed Championship (as a heel). Y2J was chosen to face HHH at Mania.
The other Wrestlemania plan was for Austin and Rock to go at it for the third time. It was even teased at the Royal Rumble, when Austin told Rock he was 2-0 against him at Mania. However, plans were changed again once Hogan, Hall and Nash signed for WWF. A huge match like Austin vs Hogan or Rock vs Hogan becoming more than just a possibility for WWF, plans for Round III of Austin vs Rock were put on the shelf for a better occasion (WM19).
Austin was offered Hogan at WM. However, Austin flat out refused, citing personal differences between him and Hogan during their tenure in WCW. Rock, on the other hand, was more than willing to work with Hogan.
So, this still left Austin without an opponent. He was offered Scott Hall. However, Austin was reluctant to work with him, due to his past troubles with alcohol. He eventually accepted. He was convinced, much like the rest of the company was, that Hall wouldn't make it to Wrestlemania. The feeling within the organization was that sooner or later Hall's demons would eventually catch up with him and that he'd get fired for it. He was then offered to wrestle an opponent of his choosing. Austin wanted Chris Benoit. He cited Benoit as one of his favorite performers in the business. However, Benoit was nowhere near ready to wrestle, as his rehab would take almost a full year year to complete. He then picked Angle, claiming he'd be more than happy to wrestle him. So the unofficial plan was for Austin to take on Angle as contingency plan, should Hall fail to appear. However, much to everyone's surprise, Hall remained sober in the entirety of the road to Wrestlemania, and the match took place. The contingency plan was out.
Sting vs Kurt Angle
Mr Perfect vs Kurt Angle
Before the proposed Angle/Austin match, the earliest idea for Kurt Angle to have a match against Sting. Steve Borden was intrigued, but came to the realization that his potential WWE Career would be a disaster, citing fellow former WCW superstar as example. Talks were only semi-serious because of this, and plans were dropped (same reason he didn't show up at WM21 & 27).
Mr Perfect returned at the Royal Rumble. He greatly impressed WWE Officials and was offered a contract. An idea was for him to take on Kurt Angle (whom Perfect hit with a Perfect Plex dring the Rumble match). However, Perfect did not take part of WM for some reason. He was relegated to a Sunday Night Heat tag team match (Perfect, Test and Lance Storm vs Scotty 2 Hotty, Albert and Rikishi.)
Kane vs Kevin Nash
Nash was to have to have a match at WM against Kane. However, with Scott Hall being a time bomb, Nash was told by Vince to keep an eye on Hall. He was to accompany Hall to the ring at WM, and should things go wrong, take his place. This meant that his role was reduced to that of contingency for Hall, hence why he didn't have a match that night.
Kane was then offered Angle as the company was really impressed with their work during an episode of RAW. WWE had at last found an opponent for Kurt.
Edge vs William Regal
The two had been feuding for months. The idea was for Edge to get the IC belt from Regal at WM18. However, Edge was replaced with RVD when it was deemed the matches were too unexciting.
Wrestlemania XIX
The Rock vs Goldberg
After Rock finished his full time career as a superstar in order to transition into becoming a movie star, he still wanted to do make compete at WM events, but only for "Once in a life time" occasions, such as Hogan the previous year (and John Cena a decade later, but that one turned out to be so profitable for WWE that it occurred TWICE in a lifetime). He wanted to face Bill Goldberg at Wrestlemania. One problem, though:Contract negotiations stalled and Goldberg ended up signing shortly before the event. It was too late to do a proper buildup. Goldberg showed up on RAW the next night. Problem is, he signed two years after the end of WCW. The momentum was gone, fans didn't care anymore, and the way he was written was abysmal. Moreover, I think one of the reasons Vince wanted to sign him so badly is because they wanted a Goldberg / Austin at WMXX , but Austin was forced to retire at WMXIX due to his growing physical problems. Austin had to settle with being the special guest referee during the Brock vs Goldberg stare down contest.
John Cena vs Jay Z
Cena was to challenge Jay Z in a rap battle at Wrestlemania, but plans fell through when neither men showed up that night.
Triple H vs Austin
Triple H vs Kevin Nash
With Steve Austin set to return in time for Wrestlemania 19, he was set to face Triple H. Triple H laid the groundwork by having him "pulling an Austin" and leaving on RAW, and by objecting to Austin winning the RAW Superstar of the Decade on the 10th Anniversary edition of RAW. These plans were in the works while Rock / Goldberg was still a possibility. When it became clear that it was no longer the case, Austin and Rock then agreed to face each other.
This left Trips without an opponent. He wanted Kevin Nash. Much like Austin wanting to face Benoit the previous year, Nash was still unavailable due to rehab. He had to settle with Booker T.