Random cookies probably wouldn't suffice. Evercookie[1] uses thirteen different storage mechanisms, making it almost impossible to delete.

[1] - https://github.com/samyk/evercookie