Smaller startups/companies are less likely to check with your previous employers. Maybe try more of them.
When you say you can't find a new role, are you not getting any interviews or are you not landing the jobs post interview? It could be that you need to work on your interview skills. Or it could be that you need to retool your skill sets. There is not enough info to say much on that.
Again, I've never experienced black listing on the interview side. But, depending on the community, people do talk. If someone knows people at a previous employer of yours, they might ask them about you.
Also, it matters how you present being fired to the potential new employer. It is viewed as more risk to take on someone who got fired vs someone who left on their own terms.
Best of luck.