First off, you need to know what is the accuracy rating of the probe. There is quite a range of quality in probes on the market. Generally, the higher the accuracy, the higher the price. Some probes read consistenly to within 0.05 pH while really good ones will be accurate to within 0.005 (these probes cost several hundred dollars). Most true "laboratory quality" probes are accurate to within 0.01 pH, but the use of the term "lab quality" is up to the merchant and there is no regulation to control this.
Second, there is a great range of how rapidly probes read the pH values, which is something you need to be keenly aware of when you calibrate. The function is an asymptotic one. So in theory, you never actually reach the final value. Practically speaking though, a high quality fast probe will pretty much settle after two minutes, while a slow one will take at least five. The age of the probe has a great deal of influence on this, and shelf storage is part of the aging process. That's why it is important to know how "fresh" is the probe that you purchase. Nearly all high quality probes have an indicated date of manufacture.