From my understanding each follow is just another note send on the network, just like updating your relay list or posting something for others to see. If you load into a new client it will need to read all your notes to check for follows etc. Your own relay might speed this up but other relays shouldn't delete your notes. Not sure what the policy is on relays pruning, deleting etc.