I was an entry level worker when I started working with a company in my town. I got laid off because my performance was not up to expectations.
After 4 years of success outside that company, I applied to them again. When I followed up with the CEO about my application, he told me they will not look at my application because of what happened in the past.
I don't know what I should I do about this - what can I do to successfully apply to this company?
If the CEO of the company is telling you that the company has a policy that they don't want to rehire employees that they previously had to let go because of performance problems, you probably don't have any options. It's perfectly reasonable for the company to take your prior performance into account-- I can't imagine that any legal system would ban that sort of thing. It may be unwise to block poor performers indefinitely since people do grow and change over time but that's the sort of potentially unwise thing that companies are pretty free to do. Realistically, you'll want to focus your job search elsewhere.
This is, unfortunately, the sort of thing that happens when you burn bridges by performing poorly. The company gave you a chance, it didn't work out, and they're not interested in giving you another chance.
Image this situation:
You work for Company A and get fired for poor performance. A few years later you apply to company B. They call your previous employer and find out that you performed poorly. They need to evaluate how accurate and relevant is that prior poor performance. They have to determine if they can trust that poor recommendation.
Now to your case:
Company A is also Company B. They have access to your entire file, not just a one line report from the previous employer. If they weren't allowed to reject you for the new position, there would not be a reason to ever call references.
Unless you can convince them that you have changed, or the new position is unrelated your previous position, it i unlikely they will hire you. It is best to move on.
Don't feel bad, for one thing! There are even companies who will only ever interview a person a single time (or round), and will not do so again regardless of time passing. For good or for ill, companies are hard-pressed to ignore HR policies unless given exceedingly good reason to.
To understand why in this case, just consider if you had decided to hire back an employee that previously had been let go. What if they didn't work out again?
People are naturally loss-averse in situations like this, and even if you have a sterling 10-year record in between this is often impossible to overcome. Sure, you might make a wonderful addition to any team now, but the fact is that your chance of not doing well is more than 0% (everyone's is!), and the perceived penalty for such failure to the person doing the hire is more extreme than ever.
While research and logic can at times indicate that failing to hire someone who would be a success is worse than taking a chance and hiring someone that doesn't work out, in practice this is not true - because a missed opportunity is usually invisible, but a hiring decision that goes bad is noticed, analyzed, blame assigned/noted, remembered, and drags on unpleasantly for days, weeks, or months. Its a wonder anyone ever hires anyone!
So really, you will be happier and more successful if you just move on to making a better first impression somewhere else. If nothing else, it is usually more satisfying to think, "I'll show those bastards!" rather than "Take me back, I swear I've changed." Onwards and upwards, friend!
Become an expert in your field to the point that that company would have to hire you because of how damn important you have become. Or marry into the CEO's family (or other high level employee with pull).
If the CEO has personally said no to you, you have no realistic chance outside of those two. And even those two situations are not foolproof. Some people would not easily swallow their pride in the first case, and some people will not bend to family pressure in the second.
Move on. Use it as a personal learning point, and find a different location to apply to.
Try
While I agree with the other answers, I feel they're missing one important aspect - trying.
While there may be little chance of success with a bit of an attempt, there's even less risk involved - as long as you're not too forceful or persistent, it's unlikely to significantly change their opinion of you (unless it's positively).
The cause
But first, note that an important aspect here is what the cause of your below-expectation performance was. Or, more importantly, what they think the cause was.
If the cause was, for example, lacking knowledge required to do this job, they might be able to test this in an interview setting (assuming they believe they can do so better than they did the first time around), and you may have success if you try. And the same applies if you're applying to a different type of job.
If, on the other hand, it was caused by (or they think it was caused by), for example, laziness, you're less likely to have much luck.
Back to trying
Now onto the actual attempt.
This may differ significantly based on the method they used to contact you.
If by e-mail (and you haven't replied yet), this is probably the easiest.
You can probably reply with something like:
I appreciate your honesty.
I believe I have matured a lot and have learnt a lot about {whatever you do} in the last 4 years and have made significant contributions to {whatever domain you work in} (which I firmly believe my references will agree with) and I would greatly appreciate being given another consideration.
However, I would respect your decision to not reconsider my application, if you choose not to do so.
(obviously along with appropriate headers and footers and customized to take into account whatever factors contributed to you having been laid off, but don't make it too long, and don't just copy the above - you should be able to justify any statements made)
Disclaimer: I'm not exactly the most skilled with language.
If contacted by phone or you've already replied, it could be a bit more difficult.
Closing note
From the company's perspective - people don't typically change that much in 4 years (although they can learn quite a bit). You can always try again in a few more years, if you're still interested.
