When you find yourself trying to remember a show (or any works) that's on the tip of your tongue but just out of reach, come here - the collective brain of the TVTropes community can probably help. Post all the details you can remember (examples help). If you're looking for a trope, head over to Trope Finder. Have general questions about tropes? Visit Ask The Tropers!
This is probably not it at all, but I keep coming back to either something from the Tortall Universe or Lloyd Alexander
Um... potentially? I guess it's hard to tell from the pages of those works.
I know that as a child I started to read the first of those books about that Alanna girl but gave it up because the stuff about periods confused me. The book that I'm describing wasn't really a children's book and wasn't concerned with courtly life and stuff relating to nobles and knights, it was more to do with travellers. I don't know if that counts as evidence for or against your suggestions.
Thanks for suggesting stuff though! :)
We have a trope page about people who are immune to/can cancel out magic. Have a look at that and see if anything rings a bell.
I think it is one of those Sword of Truth books! I did check the Anti-Magic page earlier but there were so many examples and they were hard to match up with the book I remembered. The Sword Of Truth character page has a White-Haired Pretty Boy and Dumb Muscle character as well as the Anti-Magic girl and it all seems to fit.
Anyway, thank you all very much for responding!
Edited by HeartOfAnAstronaut

I read a part of this book around 2003, I was on a holiday and being a sulky 12 year old so I read a bit of someone else's book and obviously I have no idea what it was, now.
It was a fantasy book set in a medieval style world and it was pretty thick, I think. I'm also pretty sure it was part of a series, and there wasn't very much world building so I don't think it was the first in the series (i.e. a lot of that setting stuff was already established in books I haven't read). There were a few viewpoint characters, one of which was a girl who meets up with a man with white hair. She was being chased, and at some point they went to a market in a big city, and he pulls her into a corner to kiss her, so that they don't get recognised. It later implied that they had sex but I didn't read enough of it to learn more about their relationship. I'm pretty sure the man rode a horse and had either green or blue eyes. I can't remember why the girl was being sought after.
One of the viewpoint characters seemed like he was being set up to be the villain, he was like a giant or something and had the mind of a child (I think?) and I think that he killed people but didn't understand that this was wrong.
The main thing that I think someone will recognise is this: one of the main characters (possibly the girl, possibly someone else) had some kind of immunity to magic, or ability to cancel it out as a special power. This ability was explained by someone who used a metaphor to do with stars and being able to see stars in the night sky, though I can't remember the details. They made it sound like this ability was important to the world somehow.
Oh, and the cover of the book I read was all black, with a landscape picture in a square/rectangular frame and gold text. Don't worry if this physical description doesn't sound familiar, you might have read a different edition. I have no idea where the book I read came from, only that it was in English. I can't remember the spellings used.
Edited by HeartOfAnAstronaut