Define the 5000 as a soft limit. Define something like 10,000 or "100 days after reaching the soft limit" as a hard limit.
When a user hits soft limit, you keep storing their submissions, but you don't let them see it unless they upgrade the subscription/buy more resources (Mailchimp's Blocks pricing strategy seems sensible to me). When a submission is received after hitting soft limit, you send your user an email telling them that they received a form submission, but they cant view it till they upgrade. (You keep notifying them). You can aggregate those notifications daily/weekly after the first few to reduce costs.
When the hard limit is reached, you stop storing those entries. And send the user 1 email telling him that you changed behaviour.