The official artbook and guidebook gives information on how Phoenix had to be defeated; 'Its body was wreathed in flame. You defeated it by plunging it into a lake'. This indicates that Wander was not able to climb its body straight away. Interestingly, in all released screenshots of Phoenix, Wander is seen riding Agro. So it can be assumed she was vital to this battle.
According to an old Team Ico Gamers Blog post, Phoenix was removed for being overpowered and also because it required a huge arena, because of its attacks.