The only real penalty for having tons of fields is that after saving a record with a large number of searchable fields, you may not be able to search on it for a longer period of time (because there's more fields to process). However, salesforce.com uses a very efficient search engine. It really doesn't matter if you have 10 fields to search or a thousand. The system uses an efficient Lucene search engine, and is capable of returning results usually in a fraction of a second, even with many hundreds of millions of rows in a table. Part of this efficiency is how records are indexed, as well as the maximum number of records that a SOSL call can return; it aborts early as soon as it reaches the limit, rather than continuing through all records. Keep in mind that the "ALL FIELDS" operator only searches indexed fields, not literally every field on the object.