If you care for performance, you should not combine a linear search with another linear search; with the resulting time complexity can’t be fixed with parallel processing when the lists get large.

You should built a data structure which allows efficient lookups first:

Map<List<?>,Map<String, Object>> inputKeys = inputRecords.stream()
    .collect(Collectors.toMap(
        m -> Arrays.asList(m.get("ID"),m.get("Email")),
        m -> m,
        (a,b) -> { throw new IllegalStateException("duplicate "+a+" and "+b); },
        LinkedHashMap::new));

List<Map<String,Object>> matchinRecords = dbRecords.stream()
    .filter(m -> inputKeys.containsKey(Arrays.asList(m.get("ID"),m.get("Email"))))
    .collect(Collectors.toList());

matchinRecords.forEach(m -> inputKeys.remove(Arrays.asList(m.get("ID"),m.get("Email"))));
List<Map<String,Object>> notMatchinRecords = new ArrayList<>(inputKeys.values());

This solution will keep the identity of the Maps.

If you are only interested in the values associated with the "Email" key, it would be much simpler:

Map<Object,Object> notMatchinRecords = inputRecords.stream()
    .collect(Collectors.toMap(
        m -> m.get("ID"),
        m -> m.get("Email"),
        (a,b) -> { throw new IllegalStateException("duplicate"); },
        LinkedHashMap::new));

Object notPresent = new Object();
Map<Object,Object> matchinRecords = dbRecords.stream()
    .filter(m -> notMatchinRecords.getOrDefault(m.get("ID"), notPresent)
                                  .equals(m.get("Email")))
    .collect(Collectors.toMap(
        m -> m.get("ID"),
        m -> m.get("Email"),
        (a,b) -> { throw new IllegalStateException("duplicate"); },
        LinkedHashMap::new));

notMatchinRecords.keySet().removeAll(matchinRecords.keySet());

System.out.println("Matching Records: " + matchinRecords.size());
matchinRecords.forEach((id,email) -> System.out.println(email));

System.out.println("Non Matching Records" + notMatchinRecords.size());
notMatchinRecords.forEach((id,email) -> System.out.println(email));

The first variant can get extended to support more/other map entries easily:

List<String> keys = Arrays.asList("ID", "Email");

Function<Map<String,Object>,List<?>> getKey
    = m -> keys.stream().map(m::get).collect(Collectors.toList());

Map<List<?>,Map<String, Object>> inputKeys = inputRecords.stream()
    .collect(Collectors.toMap(
        getKey,
        m -> m,
        (a,b) -> { throw new IllegalStateException("duplicate "+a+" and "+b); },
        LinkedHashMap::new));

List<Map<String,Object>> matchinRecords = dbRecords.stream()
    .filter(m -> inputKeys.containsKey(getKey.apply(m)))
    .collect(Collectors.toList());

matchinRecords.forEach(m -> inputKeys.remove(getKey.apply(m)));
List<Map<String,Object>> notMatchinRecords = new ArrayList<>(inputKeys.values());

You could loop over the List one time and compare Maps in each list. This would cut your Big-O runtime in half -- assumes that the Maps are in the proper order (i.e., via LinkedList).

public boolean compare(List<Map<String, Object>> A, List<Map<String, Object>> B) {
    // check size first
    if (A.size() == B.size()) {
      // if the Maps are abstracted into a POJO you could implement Comparator on that POJO.  In the meantime you can sort manually
      // sort A
      Collections.sort(A, new Comparator<Map<String, String>>() {
        public int compare(final Map<String, String> o1, final Map<String, String> o2) {
            // optionally, you could use any method of sorting here... single field like an ID, multiple fields compared, sums, etc.
            return o1.get("field").compareTo(o2.get("field"));
        }
    });

      // sort B
      Collections.sort(B, new Comparator<Map<String, String>>() {
        public int compare(final Map<String, String> o1, final Map<String, String> o2) {
            return o1.get("field").compareTo(o2.get("field"));
        }
    });


        for (int i = 0; i < A.size(); i++) {
            // get map from A & B
            Map<String, Object> aMap = A.get(i);
            Map<String, Object> bMap = B.get(i);

            // check equality of Maps
            if (!aMap.equals(bMap)) {
                return false;
            }
        }
    } else {
        // Data reconciliation failed :: Data size mismatch
        return false;
    }

    // if we get here then all was good
    return true;
}

just use equals:

if (!map1.equals(map2)) {
    //they differ
}

you will have to implement equals (and hashCode!) on MyCustomObject, since (if I understand correctly) the objects will have the same content but different identity (the default equals just compares the pointers - i.e., the memory address in which the object live in).

Quick Answer

You should use the equals method since this is implemented to perform the comparison you want. toString() itself uses an iterator just like equals but it is a more inefficient approach. Additionally, as @Teepeemm pointed out, toString is affected by order of elements (basically iterator return order) hence is not guaranteed to provide the same output for 2 different maps (especially if we compare two different maps).

Note/Warning: Your question and my answer assume that classes implementing the map interface respect expected toString and equals behavior. The default java classes do so, but a custom map class needs to be examined to verify expected behavior.

See: http://docs.oracle.com/javase/7/docs/api/java/util/Map.html

boolean equals(Object o)

Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This ensures that the equals method works properly across different implementations of the Map interface.

Implementation in Java Source (java.util.AbstractMap)

Additionally, java itself takes care of iterating through all elements and making the comparison so you don't have to. Have a look at the implementation of AbstractMap which is used by classes such as HashMap:

 // Comparison and hashing

    /**
     * Compares the specified object with this map for equality.  Returns
     * <tt>true</tt> if the given object is also a map and the two maps
     * represent the same mappings.  More formally, two maps <tt>m1</tt> and
     * <tt>m2</tt> represent the same mappings if
     * <tt>m1.entrySet().equals(m2.entrySet())</tt>.  This ensures that the
     * <tt>equals</tt> method works properly across different implementations
     * of the <tt>Map</tt> interface.
     *
     * <p>This implementation first checks if the specified object is this map;
     * if so it returns <tt>true</tt>.  Then, it checks if the specified
     * object is a map whose size is identical to the size of this map; if
     * not, it returns <tt>false</tt>.  If so, it iterates over this map's
     * <tt>entrySet</tt> collection, and checks that the specified map
     * contains each mapping that this map contains.  If the specified map
     * fails to contain such a mapping, <tt>false</tt> is returned.  If the
     * iteration completes, <tt>true</tt> is returned.
     *
     * @param o object to be compared for equality with this map
     * @return <tt>true</tt> if the specified object is equal to this map
     */
    public boolean equals(Object o) {
        if (o == this)
            return true;

        if (!(o instanceof Map))
            return false;
        Map<K,V> m = (Map<K,V>) o;
        if (m.size() != size())
            return false;

        try {
            Iterator<Entry<K,V>> i = entrySet().iterator();
            while (i.hasNext()) {
                Entry<K,V> e = i.next();
                K key = e.getKey();
                V value = e.getValue();
                if (value == null) {
                    if (!(m.get(key)==null && m.containsKey(key)))
                        return false;
                } else {
                    if (!value.equals(m.get(key)))
                        return false;
                }
            }
        } catch (ClassCastException unused) {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }

        return true;
    }

Comparing two different types of Maps

toString fails miserably when comparing a TreeMap and HashMap though equals does compare contents correctly.

Code:

public static void main(String args[]) {
HashMap<String, Object> map = new HashMap<String, Object>();
map.put("2", "whatever2");
map.put("1", "whatever1");
TreeMap<String, Object> map2 = new TreeMap<String, Object>();
map2.put("2", "whatever2");
map2.put("1", "whatever1");

System.out.println("Are maps equal (using equals):" + map.equals(map2));
System.out.println("Are maps equal (using toString().equals()):"
        + map.toString().equals(map2.toString()));

System.out.println("Map1:"+map.toString());
System.out.println("Map2:"+map2.toString());
}

Output:

Are maps equal (using equals):true
Are maps equal (using toString().equals()):false
Map1:{2=whatever2, 1=whatever1}
Map2:{1=whatever1, 2=whatever2}

If both of your lists can contain unique items you could merge them together into a Set<> to remove duplicates. Then create a List<> again for your desired output:

Set<Map<String,String>> set = new HashSet<>();
set.addAll(customerDetails);
set.addAll(accountDetails);

List<Map<String,String>> combined = new ArrayList<>(set);

System.out.println(combined);

Output:

[{Account=1049, name=Tom, id=2}, {Account=1052, name=Mary, id=3}, {Account=1050, name=Andy, id=1}]

Let's summarize some of the variations on this, as the best solution only emerges after reading the other answer and the comments.

The simplified problem from the question is something like this. Given two maps:

Map<Integer, String> mapA = Map.of(1, "a", 2, "b", 3, "c")
Map<Integer, String> mapB = Map.of(5, "a", 6, "d", 7, "c")

find the keys of mapB that correspond to values that occur in both maps. The question had a start at a solution which was this (edited for clarity):

Set<Integer> result = mapB.keySet().stream()
    .filter(keyB -> mapA.keySet().stream()
                        .filter(keyA -> mapA.get(keyA).equals(mapB.get(keyB)))
                        .count() > 0)
    .collect(toSet());

Essentially this is like two nested loops that loop over the keys of each map. The inner loop gets the corresponding values for each key and counts the number of matches. If there's at least one match, key gets passed through the filter to the result.

The OP wasn't satisified with this and requested improvements, particularly about algorithmic complexity. As mentioned in the comments, the real problem might have 15,000 map entries. This algorithm is O(n^2), and it does begin to degrade noticeably with this number of mappings. There are some minor ways this could be improved, such as by using anyMatch instead of filter and count > 0, but these aren't necessary given the alternative proposed in the answer from Eritrean:

Set<Integer> result = mapB.entrySet().stream()
    .filter(entry -> mapA.values().contains(entry.getValue()))
    .map(Map.Entry::getKey)
    .collect(toSet());

This is nicer, as it uses the contains operation on mapA's values() view, replacing the inner stream of the previous solution. However, the values of a map aren't indexed, and so the only way that contains() over the values of a map can work is (potentially) to search every entry. This is somewhat better than before in that if a match is found, contains() can return immediately; but if a match isn't found, it must search all the values of the map. Therefore, on average, this variation still runs in O(n^2) time.

One way to mitigate this is to pull mapA's values into a HashSet. This will reduce the contains() check from linear time to constant time, reducing the overall complexity from O(n^2) to O(n). That would look like this:

Set<String> aValues = new HashSet<>(mapA.values());
Set<Integer> result = mapB.entrySet().stream()
    .filter(entry -> aValues.contains(entry.getValue()))
    .map(Map.Entry::getKey)
    .collect(toSet());

This is a big improvement, but it turns out that using streams isn't necessary at all. Returning to the problem statement, it has the clause "... values that occur in both maps." This is essentially doing a set intersection on the values collections. The way to do intersection in Java is with the retainAll method. That is, given two collections x and y, doing x.retainAll(y) will retain in x only those elements that also occur in y, and it will remove others. That's essentially a set intersection. To do this, retainAll typically must call contains repeatedly on y, so it's a good idea to make sure that operation is fast -- like with a HashSet.

OK, if we intersect the values collections, that gives us values -- but we want the keys. In particular, we want the keys of mapB. How do we do that?

It turns out that the values() view of a map supports removal -- which retainAll does -- and if a value is removed from it, that removes the corresponding entry from the underlying map. In this case we can start with mapB (or a copy), get its values() view, call retainAll with mapA's values that we had previously loaded into a HashSet. That leaves in mapB only the entries that have values in common with mapA. Since we're interested in the keys, not the entries, we just get the keySet() view. That code looks like this:

Set<String> aValues = new HashSet<>(mapA.values());
Map<Integer, String> mapBcopy = new HashMap<>(mapB);
mapBcopy.values().retainAll(aValues);
Set<Integer> result = mapBcopy.keySet();

This demonstrates how it's possible to use collections bulk operations on collection views to accomplish certain tasks more simply than using streams.

Map#equals does not care about the order. As long as your 2 maps contain the same mapping it will return true.

Map#equals uses Set#equals method, applied to the entry set. Set#equals contract:

Returns true if the specified object is also a set, the two sets have the same size, and every member of the specified set is contained in this set (or equivalently, every member of this set is contained in the specified set).

Note: this assumes that your CourtCase objects have proper equals and hashcode methods to be compared.