Odds are it was the traditional "contact cement" a permanent mustard-yellow solvent based cement. Various petrochemical solvents like acetone probably will help (don't dare use anything that can make a spark around this, and don't breath it, use good ventilation) and there are some generically called "rocket fuel" that might do it faster.
There's one miracle in a spray can called "Klean Strip" brand "Premium Stripper" which will teach you a new respect for rubber gloves, but works miracles. Read and follow the warnings--it's great stuff but like any power tool, you don't want to use it on yourself.
After that, you're back to a paint scraper or cabinet scraper and sanding.