I don't think there's a "hard and fast" rule you could apply here, it would have to depend on the service. I'd probably do something along these lines:
* Warn the user with as much notice as possible that they're over or close to the limit of their downgraded plan. It should be painfully obvious to the user that they're about to lose their extra privileges and data. (a red bar with warning always displayed along top of site, for example)
* On the day of the downgrade, send them another email saying the changeover is imminent.
* Actually don't downgrade them for a couple of days, but keep the message up.
* After those couple days, do switch over, and don't allow any write accesses other than deletes until the user has cleared the excess. Make sure your app handles this gracefully. If your app is mostly write once, read many, then put random data over the limit (their most-used files?) into "holding" where they can't get to it until they delete files to get under the quota. (and give a hint that they wouldn't have this problem with the more expensive account type)
* If they don't clear out their stuff after 2-4 weeks, just automatically delete enough data to enforce the quota. Email them a final warning a few days before the deletion.
But maybe that's just me and my naturally customer-friendly point of view. :)