They moved into Velocity before they were taken over by BT. Prior to that they had the main premises at Terry St and also had 'Internet House' at Victoria Quays. IIRC it meant that some staff would spend 20mins going between buildings. Not to mention that some of the Network equipment was at a third location in Sheffield, (4 if you include telehouse london, locations) so you can imagine a lot of time was wasted 'travelling'.
More space was needed purely for more staff as the ISPs took on new customers.
When I joined PN in early 2003 iirc they only had about either 60,000 broadband customers, as adsl was in its infancy and considered a luxury and when theyd not that long been in Terry St and the core CS relations team headed by Ian Wilde only had about 6 staff. (There were plenty of others doing other things)
Ive not been to PN Towers for a while, but last time I was there, there was a dedicated team for dealing with BTw escalations, probably taking up about 8 seats?
IIRC Zen went through a similar phase as well with locations, and Im sure theyve been through about 3 moves in the same period.
I was pre-reg'd with Zen but went with PN in the end mainly because of support + hours (and the freebie cgi webspace).
Most ISPs will have seen similar growth, and I should imagine that the demand for broadband in the late 00's meant more staff needed which in turn requires more space.... and of course more network equipment.