Since the election was a two-stage ballot, Schwarzenegger could also have lost by having Gray Davis win the yes-or-no question on the recall itself. IOTL, the margin on the recall question was 10.8%, a convincing win but smaller than the 17% margin on the replacement election question.
Davis could have done better on the recall question had California's Democrats agreed to clear the field for him and bet everything on the first question, but probably not well enough. IOTL, exit polls indicate 3-4% of voters voted Yes on the recall but voted for Bustamante in the replacement question, which isn't enough to close the gap even if all of them would have voted against the recall if there were no serious Democratic candidate on the replacement ballot. Davis could probably also have picked up a few more percentage by not having the recall campaign divided between defending Davis and promoting Bustamante as a replacement.
Another path would be for Garamendi rather than Bustamante to run as the Democratic replacement candidate. The exit poll showed Bustamante with a 58% unfavorable rating in the 2003 recall election, and Garamendi did 11% better than Bustamante in the 2006 general election where Garamendi ran for Lieutenant Governor against Tom McClintock and Bustamante ran for Insurance Commissioner against Steve Poizner.
There are also a couple possible PODs related to the Republican field. Richard Riordan could have stayed in the race instead of clearing the field for Schwarzenegger, which could have split the vote of Schwarzenegger OTL supporters. Alternately, the Republican field could have cleared early and completely for Schwarzenegger, making it easier for the Schwarzenegger's opponents to portray him as too conservative without McClintock in the race to serve as a contrast.