How can this website reidentify me even after deleting all of my browser's history and using a VPN?

The website is using IndexedDB, for which MDN writes:

IndexedDB is a way for you to persistently store data inside a user's browser. Because it lets you create web applications with rich query abilities regardless of network availability, your applications can work both online and offline.

Not clearing it sounds like a bug in Firefox indeed, but apparently the developers feel otherwise. Like in March 2015, someone wrote:

But even when you delete all your history information the data from IndexedDB persist.

The right way to delete this data is by going to about:permissions address, look for the domain and pressing the Forget About This Site button.

While about:permissions does not work in my Firefox 55, going into Tools, Page Info, Permissions I get the button "Clear Storage":

Even worse, neither the greyed-out "Use Default: Always Ask" in the above screen capture, nor enabling "Tell you when a website asks to store data for offline use" in settings, Advanced, Network, have any effect to avoid storage:

It seems the following from August 2011 may still apply (where "[only]" is added by me):

By default in Firefox 4, a site can use up to 50MB of IndexedDB storage. [Only] If it tries to use more than 50MB, Firefox will ask the user for permission [...]

In Firefox for mobile devices (Google Android and Nokia Maemo), Firefox will [only] ask for permission if a site tries to use more than 5MB [...]

To disable it altogether, go to about:config and disable dom.indexedDB.enabled. However, beware that such might affect plugins/add-ons as well, which seems to be why some want to remove that option, for which someone noted in May 2016:

Until IndexedDB is handled in the same way as cookies with respect to accepting/clearing and third-party behavior, this pref should exist.

(One may find dom.storage.enabled interesting too...)

As noted by Arjan it's unfortunately easy to leave site-data installed currently. This is improving somewhat with the preference UX redesign in FF57.

For example, under "Privacy and Security" there is now a "Site Data" section:

Clicking the site data "settings" will allow you to remove site-data for a specific origin:

This will remove data stored in IDB, Cache API, etc. It will also remove cookies for the origin:

(Sorry for not making this a comment under Arjan's answer, but I wanted to include these screenshots.)

Disclaimer: I am a Mozilla employee

Edit: Please read the comment by Ben Kelly before messing with any files in your profile.

Since there is no solution inside Firefox, one can easily implement a temporary fix for this outside of Firefox. IndexedDB files are stored in the directory <profile>/storage/default. By emptying this folder (for example though a scheduled script) you can recover full control over your data and how long it persists. Since each website is stored in a separate folder, you could even implement a whitelist/blacklist or basically every policy you want, given you have some programming experience.

It's not a nice solution and no excuse for Firefox developers to continue to postpone a proper solution for this. (Bugreports exist for years now!)

And be aware that the data format and location might change over time. For example, in a previous version, all IndexedDB data was stored in a single SQL file.