I had a requirement to quote a Salesforce implementation for a client. It has a lot of data with low license count. Initially it was in the 200.000 records + Campaigns and Campaign Members, which the 1GB you get in an enterprise edition was enough. The problem is that now the requirement is including over 4 millions contacts with future Campaigns and Campaign Members to consider. Issue is that with something around 2KB per Contact and 1KB per CampaignMember data needed will be over 10GB, by my estimates. The number of Enterprise/Unlimited licenses needed for this is prohibitive. Adding chunks of 500MB (which there is no official number in SF documentation, but Internet search says it's as an Enterprise Edition) also goes WAY off budget.
So what technical options would I have here to cope with this requirement+budget? They already have Salesforce so they are not too keen onto moving to a different platform (I understand storage in SugarCRM, Zoho or Saleslogix is a lot cheaper). My approach so far is to do a Heroku integration, store everything on Heroku and access it through SF and manage the logic there. The integration should be quite as challenge but not as costly as that many licenses. There are requirements for other integrations in the way (like Amazon) so it made sense.
So in short the question is, how would you handle this situation? What is a good way to handle a SF instance that has too many records (and not historic records unfortunately, so SF new archiving solution doesn't address this).
PS: the client is well aware that changes to the scope/requirement affect the budget. I still need to look for different options.