In my experience, there are two extremely common types of challenges in role playing games. These two categories are
- challenges against a characters skill/ability,
- and challenges against a characters morals/desires.
Let's look at the first one, the one you obviously have hid a road block with.
Challenges against a characters skill/ability
Roll Manipulation + Subterfuge...
When do we challenge the characters' skills and ability? The answer is pretty straight forward; every time we tell them to make a roll. Now that we have that out of the way, I would propose another, much more important question; why do we challenge the characters' skills and abilities?
The answer to this will probably vary from group to group, but I'm pretty sure that most people will agree that we make rolls to create suspense, or to allow the situation to take an unexpected turn. At least that is the underlying reason. Many rule books will simply say that we make rolls whenever the outcome is uncertain, but this is roughly the same.
In your game, the characters have "perfect skill", as you describe it, and they apparently always succeed at whatever they are good at. In this situation, ask yourself why you want to challenge them on their "specialty". What will it add to your game? If the player has a great time auto-succeeding, and no one else seems to mind, then go for it. But it won't add any kind of suspense or uncertainty to your game.
Whatever you do, don't "punish" the player, by making this ability pointless. He has spend some sort of resource becoming exceptionally good at something. Don't let him just sit there and regret he "wasted" points on it. Instead, use it as a possibility to make his character shine, make his character succeed where everyone else fails. The point of being good at something is to do it, after all. This will also make the character irreplaceable, which I personally believe every character should be, in any game.
Challenges against a characters morals/desires
"If you are not for me, then you are against me!" King Olaf shouts angrily at you. It seems, yet again, that you must choose sides...
Sometimes it is not about skill, but about choice. You can't fight on both sides of a war, as in the example above. This is a very efficient way to create drama, since every choice in a role playing game should be meaningful and therefore have repercussions.
A good choice can be your salvation, a bad one can be your downfall. Sometimes both choices are good, but conflict will greatly be magnified when all choices are bad.
When do we present characters with a hard choice? When we want to create drama, and when we want to let the players decide what comes next. In humble opinion, a hard choice is the ultimate storytelling aid. Have you ever seen a movie, where the hero doesn't have to make a hard choice? Wait, let me rephrase that; have you ever seen a good movie, where the hero doesn't have to make a hard choice?
Use these hard choices. Hard choices tell a better story than any single skill roll will ever do. Besides, making a player make a hard, meaningful choice, you put his character right there in the spotlight, and for a moment he is the most important person in the group.
If a character "cannot fail", then it is pointless to challenge him. But if he can't fail, then abuse it to tell great stories, where his perfection will advance the story in whatever way it must. But remember, for a story to be truly great, it must touch on something else than mere skill.
A characters skill is the players way to coerce the story in the way he wants it to go. Don't take it away from him, but remember to challenge his character on other skills as well.