You can use HashSet to store all the edges. It is fast to check, is the edge is already in set. But you should override GetHashCode and Equals. I made a simple example.

class MyLine
{
    public MyPoint P1 { get; private set; }
    public MyPoint P2 { get; private set; }
    public MyLine(MyPoint p1, MyPoint p2)
    {
        P1 = p1;
        P2 = p2;
    }
    protected bool Equals(MyLine other)
    {
        return (Equals(P1, other.P1) && Equals(P2, other.P2)) || Equals(P1, other.P2) && Equals(P2, other.P1);
    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((MyLine)obj);
    }
    public override int GetHashCode()
    {
        unchecked
        {
            return P1.GetHashCode() + P2.GetHashCode();
        }
    }
}
class MyPoint
{
    public string Id { get; private set; }
    public MyPoint(string id)
    {
        Id = id;
    }
    protected bool Equals(MyPoint other)
    {
        return string.Equals(Id, other.Id);
    }
    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != this.GetType()) return false;
        return Equals((MyPoint)obj);
    }
    public override int GetHashCode()
    {
        return (Id != null ? Id.GetHashCode() : 0);
    }
}

then you should be able to add each line like this:

public static void Main(string[] args)
{
    HashSet<MyLine> lines = new HashSet<MyLine>();
    var line = new MyLine(new MyPoint("a"), new MyPoint("b"));
    lines.Add(line);
    line = new MyLine(new MyPoint("b"), new MyPoint("a"));
    lines.Add(line);
}

Also with GetHashCode and Equals you can store all the lines in List and then use Distinct method.

public static void Main(string[] args)
{
    List<MyLine> lines = new List<MyLine>();
    var line = new MyLine(new MyPoint("a"), new MyPoint("b"));
    lines.Add(line);
    line = new MyLine(new MyPoint("b"), new MyPoint("a"));
    lines.Add(line);
    lines = lines.Distinct().ToList();
}

Use a HashSet<Tuple<Point3D, Point3D>> . Whenever you get a new edge - p1,p2, check for (p1,p2)'s existence in the set. Also check for (p2,p1)'s existence. If neither exists, add (p1,p2) and (p2,p1) to the set and use the edge.

You can further speed this up by crafting your own hash and equality functions that will see (p1,p2) as equal to (p2,p1). Don't do that unless you need to, Set operations are very quick, I doubt the improvement will be considerable.