If my previous research is wrong, what are my options ?

A lot of research is wrong for one reason or another. If a scientist finds out that a paper of someone wrote contains errors the usual process is to write a new paper. Science progresses through new papers and everyone accepts that old papers often contain errors and are overtaken by new research.

The only thing that might be research misconduct is to to forge your research results by not changing the data you publish. Given how hard it is to persue people for massive fraud it's however unlikely that anybody will argue in present day academia that leaving out one sample for understandable reasons will constitute fraud. 

An erratum might say: 

"We initually omitted one sample from our results because we believed it to be due to measurement error (or whatever rationalization you had at the time). That sample was X. Given our new research reported in paper Z we now believe that we made an error in omitting that sample and think our here proposed method has systematic flaws that lead to results like the sample."

I think this happens to many scientists. I found myself in a similar situation once - we could not have done better at the time, but we could have noticed that the tools we used were not sufficient. Fortunately, by the time we noticed we had better tools and we found that the conclusions were still valid, even if some quantitative results were pretty inaccurate. As you, I wanted to submit an erratum, but my boss insisted to include the results in another related paper instead. I still feel that an erratum would have been better, but I think he was worried that the referee would be someone who disliked him for unrelated reasons.

If I understand correctly, your paper was about a new method and it turns out that the method itself is fatally flawed. However, what you report is what comes out of the approach, and there is a problem with the basic idea which was not trivial to see. The  thing you feel guilty about is omitting the outlier from the results, but that you cannot fix anyway. Is this more or less it?

I don't think you should retract. It understand the impulse if you feel there is no value left in the paper, but it seems to me that retraction is mostly done for misconduct, if the paper contains something that is factually wrong (you wrote you did X but actually you did Y), or if your results come out of not adopting established best practices. 

An erratum would be good -because it's linked to the paper- but in your case it may be difficult to write. On one hand, the whole paper is invalidated. On the other hand, there is no factual error to correct, and a lot of papers are based on ideas which looked good at the time but are found to be wrong by later literature. Most of them I would say :) Scientists are not systematically publishing erratums when they recognize their proposed method was not as good as hoped.

In the end, I think your boss suggestion of making another paper may be the best in your case. You would be discussing why method X, which seems like a good idea, does not work after better analysis, the subject of hundreds of papers every year. The fact that you are the ones that proposed method X is no problem. If someone gets the idea of using that approach, given that it's 15 years old they will check more recent literature I hope. Nowadays it's easy to check the citing papers with google scholar.

I understand if you feel like you are hiding the fact that you had those suspicious results from the beginning, but you didn't figure out they were important until later. Also, the important thing is to correct the mistake in any form. If your boss finds the correction low priority, discuss with your colleague that did some work for for the new paper, and try to find the time to present your boss with a draft. 

If we publish a new article, as my boss wanted, I fear some people will still find the first paper and not the second one, will keep quoting it, and, god forbid, use that published method.

Can you clarify this for me?  Why would a new article make it more likely that people would find the first paper compared to the current situation wherein the only paper they could find is the first paper?