Ask HN: Startup not “giving” me my exercised shares

I was at a startup for a year and a half, one of the first employees. Since I had vested my first year of shares, I asked to exercise them. They initially told me that I couldn't, and that I could only exercise upon leaving the company. That was a ridiculous claim, and after a few weeks of back and forth and what seemed like hunting for reasons why I couldn't exercise my stock, they finally agreed that me exercising at that time was not "early exercise" and that I was able to do so.

I ended up leaving the company for other reasons. I still thought the company had value, but it didn't make sense for me to stay there in terms of my career. I sent in my exercise notice and check. All great, they cashed my check, agreed to get things worked out and to send me my stock certificate in a month.

Three months later, I e-mail them asking about the certificate. They respond with "Oops, we forgot to let you know, companies these days aren't issuing certs, and the exercise notice you filled out is legally binding, so you are all good then".

This seems ridiculous to me. I understand digital certs as opposed to paper ones, but I've never heard of anyone taking someones word for it in terms of property ownership. I have a feeling I'm getting scammed. I read that if I was promised a cert, I should get one. My plan of attack is to request a cert in some form, and contact a lawyer if that doesn't work out.

Has anyone had a similar experience? What would you do in this situation?