There are several issues here. Let's see if we can disentangle them a bit.
First, "beauty is only skin deep." I take that to be a way of reminding us that physical beauty isn't the only thing we care about in our romantic relationships. And it isn't. If the most beautiful person in the world is also the meanest most miserable person in the world, that makes for poor romantic prospects. It's possible to dislike someone intensely and know that they're beautiful, and that's compatible with physical beauty being objective. It doesn't make any problems for aesthetic judgment.
That said, it's possible to think that some things or people really are more beautiful than others without thinking that for any two people or things, either one is more beautiful that the other or else they're equally beautiful. There may be things or people whose beauty can't be fully compared. One result may be that you don't find beautiful some things that I find beautiful, and there's no question of one of us being wrong.
Romantic relationships are partly matters of choice. So are friendships, for that matter, and romantic relationships, thankfully, are usually friendships as well. If someone is my friend, I don't just abandon them if someone "better" comes along. It's not just that I feel affection for my friends. I'm also committed to them. Commitments have a lot to do with the choices that are part of romantic relationships.
You ask why someone who could choose between two equally amiable people would choose the less physically attractive one. Maybe that kind of choice comes out in speed dating and pickup situations. But most romantic relations have more dimensions than that. There's nothing strange in the idea that two people might be equally agreeable, and yet I might prefer the less physically beautiful. I might be able to see that one person is "objectively" less beautiful than the other, and yet I might just like the less beautiful person more for any number of reasons or for no reason that I can articulate to myself. This does't make me self-deceived. Whatever "ideals" beauty has, they aren't the only things that go into romantic relationships.
(And by the way: you talk about men who are in relationships with women who aren't conventionally beautiful. I assume that if there's a real question here, it has nothing special to do with men.)
The only way I can feel any sense of paradox or puzzlement about the cases you raise is if I think about romantic attachment—about being in love—in a way that seems way too narrow to do justice to the actual thing. Let's agree: if you don't find someone physically attractive at all, you probably won't fall in love with them. But if you do fall in love with them, you'll probably start to see them in a different way than you did at the outset. They will literally look different to you. The real point, however, is that being in love is a complex business. (It may also be complicated, but that's a different point.) The way lovers feel about one another involves a lot more than whether they think their lover is beautiful. That's the way it is, but it's also something to be thankful for.