The subject really says it all.
An encounter with a Lamia and her melee reach 5 shows that I don't understand how melee reach interacts with cover.
I've gotten confused about this fairly often thanks to an unfortunate interaction between the Dungeon Master's Guide and the DDI Compendium.
The basic rules, as per the Player's Handbook and the Rules Compendium, are fairly simple. Pick any corner of your square; trace lines to the corner of any one square the target occupies. If no lines are obstructed by an obstacle or an enemy, there's no cover. If one or two lines are obstructed, there's cover (aka partial cover). If three or four lines are obstructed, there's superior cover. I don't think that changes with reach.
The Dungeon Master's Guide adds optional complexity. It defines a difference between melee and ranged attacks. Ranged attacks work the same way; for melee attacks, there's cover if a line from any corner of the attacker's square to any corner of a defender's square is blocked. These rules make cover easier to establish for melee characters. The problem is that they're marked as optional, but the DDI Compendium doesn't preserve that distinction, so people look them up online and think they're part of the core ruleset.
OK. All that established, let's get on to reach.
There's a clause that says that if a creature with reach attacks through terrain that would grant cover if the target were in it, the target has cover. I.e., if an ogre is standing on one side of a small pillar, and attacks someone on the other side, that someone has cover. I think this is a poor example, because that someone would already have cover -- you can't establish four unblocked lines between a corner of any square the ogre occupies and the target.
This makes more sense if we're talking about, say, a bush -- terrain that can be occupied but that grants cover. In that case, I believe you'd take the lines you traced and if any of them passed through that terrain, the target would have cover. It's tempting to rule that something with an amorphous attack, like the lamia or a tentacle beast, would get to ignore that, but I don't think that's how it's supposed to work.