What you are experiencing is pretty normal given your approach. A random forest is an ensemble of decision trees where models are trained in parallel using bootstrapped samples (a technique called bagging). Even though the decision trees are randomized (a thorough explanation of random_state can be found in this question), they still rely on an internal criterion (such as Gini index by default in RandomForestClassifier) to split the nodes and define decision paths. The fact that some of your samples are consistently being misclassified regardless of the random state is an indication of their objective difficulty when using this specific criterion.
Therefore, do these samples which are always wrongly predicted deserve a particular attention or is it kind of logic ?
You are absolutely correct with your first thought. Paying particular attention to wrongly predicted samples in ensembles is the goal of a technique called boosting. The main idea is to train ensemble models in sequence, with new learners focusing on data points that the rest of the ensemble has previously failed on. A great overview of ensemble approaches is presented in this answer, which I highly recommend.
As far as boosting algorithms go, there are different flavors as well: you might want to try sklearn's AdaBoost and gradient tree boosting implementations, or XGBoost. These may help you finally defeat those pesky hard-to-classify samples, but be aware that bagging (your current model) has its own perks that boosting lacks.
