It took until the week which ended on the 11th of May 2003 before DVD rentals outperformed VHS tapes for the United States. (Source: SDA VidTrac)
DVD players were sold in the United States since late 1997. So this took more than 5 years and just shows it takes time for a format to take off. And DVD was adopted extremely quickly, especially compared to the previously successful VHS format.