So what's the actual problem? Are they short on disk space where the 20GB DB is too large or is there just too much history? Kentico's version history is a great way to keep things in check especially if you can't upgrade to v9.
First start with ensuring all the versioning is setup properly in Kentico and will eliminate older version history as needed.
Secondly, I'd check to see if the version history is the actual problem in the database. Run a script to see which tables have the most data in them. In the last few months I've worked with some large websites who had analytics turned on but never managed the analytics data. One database was 153GB in size. After cleaning up the analytics data to the last year or less, I was able to get the database to under 12GB. Another I just worked on last week is at 18GB but they didn't have all tracking turned on. Once I removed the history in Kentico, it cut the database back to 4GB. My guess is you'll find other tables with more data in them than the version history. Some tables to check are CMS_Email, all the Analytics_XXX tables, CMS_EventLog, Staging_Task. I also have a script which gives row counts for all tables, views and indexes.
There are other options like upgrading to v9 and purchasing RedGate but they come with an expense so I'd say use the tools Kentico provides because they work very well but make sure the tools are configured correctly before going with another solution.