I like the +1 skill point idea, but if you wanted to give them something similar to that but more unique you could try this:
Natural Bent: Half-Elves choose a single skill in which they have a natural ability. For classes in which that skill is normally a cross-class skill, it is considered a class skill. For levels of classes in which it is already a class skill, one free rank (or four ranks at 1st level) is gained in that skill.
If you want to give them a little more, you can give them a free Skill Focus feat to go with it.
Would mess with some PrC requirements, though...