To be fair, the clause in planar binding mentions it as a task the bound creature cannot complete of it's own volition. Creatures can't progress time any faster, they have no control over the completion of the task, thus it is considered open ended. That said, note that the entry in tome of magic stated that the planar binding was very carefully worded. This alone implies it's not that simple, there must have been something else in the planar binding clause that resulted in the 500 years of servitude. Perhaps it was something like "Torture 30 billion souls, to a maximum served time of 500 years". The torturing of 30 billion souls is certainly a non-open ended task, and something the fiend's capabilities enable him to progress at his own rate. The addition of the "maximum of 500 years" clause seems a bid odd for something like that though. Perhaps the fiend considered it an unreasonable request without the maximum time served.
Either way, it's not as simple as "Serve me for 500 years". Also note that the fiend isn't serving the caster's whim, he's doing a specific task, and is tasked to do it for 500 years.
He's talking about a quote from tome of magic.