If you talk to King Arthur after receiving the Quest from him, he will tell you to seek the blessing of the Lady of the Lake. (Or just have him tell you this as part of giving you the quest.) After this, your next fountain dip is guaranteed to produce Excalibur, if it does not already exist.