What are the benefits of using a business process for leads, cases, opportunities and solutions rather than defining a normal picklist to hold the record's status? Is it just so you can assign the business process picklist values to multiple record types at the same time and keep them consistent?
The Business Processes are tied to extra metadata that can drive your business logic.
For Leads, the Status is used to indicate lead-to-opportunity conversion.
For Opportunities, the Stage is used for Forecasting, and is related to Quotas and other sales-related functionality.
For Cases, the Status is used to track SLA compliance, Milestones, and to enable/disable Escalation Rules.
For Solutions, the Status drives the availability of Solutions to be attached to Cases, the Knowledge Portal, and other functionality.
In other words, you should use Business Processes, as they drive a ton of features in Salesforce. Aside from that, you'll note that these fields are required, so the user must interact with them anyways; you may as well use them for their intended purpose.