How are folk storing lots of Files on Cases?
There are different solutions as you suggested. One is using custom fields of the type file upload or use activities. 
There is indeed a document extension and this is one also capable of storing documents on a case. The advantage of the latter is that it could also store versions of the same document. 

It is not yet possible to search for documents on a case.