The general rule is that whatever is considered a chatzitza[1] for various required tevillot is considered a chatzitza for netilat yadayim as well.[2] The most basic sub-rule is that something that is stuck to the skin is a chatzitza if either it covers most of the skin or if one is makpid about it (would like to have it removed).[3] Apparently, in your case, after the initial washing, the paint was no longer on most of your hand.
The Shulchan Aruch[4] says that paint is the type of matter whose status as a possible chatzitza is subjective. If most people in the world are makpid about a particular matter stuck to their bodies, then it is a chatzitza even for the minority that is not makpid.[5] However, if a member of this minority is not makpid because people in his vocation are accustomed to having such stains, it is not a chatzitza for him.[6] The explanation is that his attitude toward the stain is actually the norm for his vocation; if others were in this line of work, they too would not be makpid. However, you are not a professional painter and presumably would appreciate getting the paint off sooner rather than later.
There is another potential ground for leniency regarding discolored skin, but it will not be helpful in your case. One of the reasons that hair coloring is not a chatzitza for women is that the coloring is not considered to have any substance (mamashut) to it.[7] However, even after washing it, the oil paint residue may have substance. (Note that dried ink is an example of a chatzitza.[8]) Therefore, as long as there is a significant amount of paint left on your hands, netilat yadayim will not be halachically effective.
If you have the chance to work more seriously on removing the paint but there still is a little that you cannot get off, then there are new factors to consider that may affect the halacha. It is possible that so little remains that you will not be makpid anymore. Additionally, the remaining color may reach the state of lacking substance, although this is hard to quantify.
Finally, let us introduce a new concept. When one has a bandage on a wound that cannot be removed because it is too painful to do so, one can wash the hand except for the covered area.[9] (Note that this is not applicable to tevilla that is required by Torah law.[10]) Similarly, if one has a wound with a scab on it, then the part of the scab that cannot be removed due to pain is not a chatzitza.[11] It stands to reason that when one has removed the paint that will come off without damaging or peeling off the skin, what remains is not a chatzitza.[12] (This idea may be theoretical in this case, as there are ways of removing all the paint.)
What should you do before you have a chance to remove all that you can? The Shulchan Aruch[13] says that when one does not have any water available for netilat yadayim, he should eat with his hands covered. Similarly, the Mishna Berura[14] says that when one cannot wash his hands for a medical reason, he should use this system. If you do not have an opportunity to do a proper job of removing the great majority of the paint within 72 minutes of when you want to eat,[15] you could do the same thing.
May you always have such noble reasons for interesting halachic questions!