Speed would be my issue for internet or "cloud" based storage. Select426 already mentioned that speed is already becoming a problem over a local network with local drives - I doubt trying to load files over the internet would be any faster.
Couple of things I'd look into for your local network. Make sure your computers and network switch are capable of gigabit speeds. You want an actual gigabit switch, not a hub. Computers that only have 100 base t network capabilities can always have a gigabit network card added for dirt cheap. On the computers/servers that hold the files - make sure they have reasonably fast hard drives (7200 rpm drives with at least 16mb of cache - preferrably 32 or 64mb cache drives) and to an extent reasonably fast machines will help as well in indexing and displaying the lists of files.
In our setup we have an actual server which serves a few purposes - Windows networking which requires anyone to logon to the network, handles sharing of regular printers for all desktops, also have a nice logon script configured which maps shared drives to all the desktops with the same consistent drive letters, also does a time sync so all machines have the same time, also runs Exchange server to handle all email, the server has a mirrored 2tb drive for primary storage of client files, and finally the server has a 9 tape IBM LTO Ultrium autoloader which does tape backups of the data (full weekly, incremental nightly).
The tape solution is getting old though and I'm looking at probably going to a hot swap drive cage to install in the server and start doing hard drive based backups swapping the drive out weekly with an offsite drive.