IF NOT EXISTS in trigger

Instead of this

... WHERE map = OLD.map ...

--  map   OLD.map  bool
--  ---   -------  ----
--  'a'    'a'     TRUE
--  'a'    'b'     FALSE
--  'a'    NULL    FALSE
--  NULL   'b'     FALSE
--  NULL   NULL    FALSE  <-- Undesired! We want this to be TRUE

try <=>, which is MySQL's answer to the SQL standard IS (NOT) DISTINCT FROM predicate:

... WHERE map <=> OLD.map ...
--  TRUE when both have the same non-NULL value or when both are NULL
--  Equivalents:
--    WHERE (map = OLD.map OR (map IS NULL AND OLD.map IS NULL))
--    WHERE (map = OLD.map OR COALESCE(map, OLD.map) IS NULL)

DROP TRIGGER IF EXISTS before_delete_concept_access;
DELIMITER //
CREATE TRIGGER before_delete_concept_access
    BEFORE DELETE ON `concept_access` FOR EACH ROW
    BEGIN
        IF (SELECT COUNT(*) FROM concept_access_log WHERE map=OLD.map 
                          AND accesstype=OLD.accesstype AND startdate=OLD.startdate AND stopdate=OLD.stopdate) = 0 THEN
            INSERT INTO concept_access_log (map, accesstype, startdate, stopdate)
            VALUES (OLD.map, OLD.accesstype, OLD.startdate, OLD.stopdate);
        END IF;
    END//
DELIMITER ;

I am not using not exists, just test if the match count greater than 0

your code runs well on my machine, what's your MySQL version?

mysql> select version();
+------------+
| version()  |
+------------+
| 5.1.56-log |
+------------+
1 row in set (0.00 sec)