Data partitioning

We offer a web based application to companies. By keeping a company_id
in the schema we differentiate the data amongst companies. e.g the user
table has a company_id field to distinguish users between companies.

However, most companies are feeling "insecure" about their data not
being stored separately from others. Also from a maintenance perspective
it seems it might be better. e.g restoring the data of an individual
company will be impossible.

Is there a way to handle this? Preferably using a single database?

Thanks,
-- Ravi.