How are these null values stored in a NOT NULL column?
What you described is not normal.

As already mentioned in comments, in Oracle databases, empty/zero-length strings are treated as NULL.

https://docs.oracle.com/cd/B19306_01/server.102/b14200/sql_elements005.htm#i59110


  Note:
  
  Oracle Database currently treats a character value with a length of
  zero as null. However, this may not continue to be true in future
  releases, and Oracle recommends that you do not treat empty strings
  the same as nulls.


Also, WHERE col = '' will never return results, because it is basically WHERE col = NULL.

It is fairly simple to reproduce these wrong results by corrupting the data dictionary manually, but I do not know what caused it in your environment just from this information.

SQL&gt; create table t1 (c1 varchar2(20) not null disable);

Table created.

SQL&gt; select constraint_name from user_constraints where table_name = 'T1';

CONSTRAINT_NAME
------------------------------
SYS_C005148

SQL&gt; insert into t1(c1) values ('');

1 row created.

SQL&gt; commit;

Commit complete.

SQL&gt; select count(*) from t1 where c1 is null;

  COUNT(*)
----------
         1


So far everything is normal.

The database can skip entire steps while executing a SQL statement based on a constraint. If you have an enabled, validated, NOT NULL constraint on col, and your predicate is col is null, the database knows that column can not contain NULL, so it will return 0 rows without actually executing the related steps. If you have an enabled, validated constraint on a column, the NULL$ column in the COL$ dictionary table for that column is set to 1. But even with a disabled, non-validated constraint, corrupting NULL$ is enough for the database to return wrong results.

The proper method for enabling that constraint should be (which obviously fails):

SQL&gt; alter table t1 modify constraint SYS_C005148 enable validate;
alter table t1 modify constraint SYS_C005148 enable validate
                                 *
ERROR at line 1:
ORA-02293: cannot validate (SYS.SYS_C005148) - check constraint violated


Now I set NULL$ manually:

SQL&gt; update col$ set null$ = 1 where obj# = (select object_id from user_objects where object_name = 'T1') and name = 'C1';

1 row updated.

SQL&gt; commit;

Commit complete.


Then run the query again:

SQL&gt; select /*+ gather_plan_statistics */ count(*) from t1 where c1 is null;

  COUNT(*)
----------
         0

SQL&gt; select * from table(dbms_xplan.display_cursor(null, null, 'allstats last'));

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SQL_ID  fjf8bcs2hhb7b, child number 0
-------------------------------------
select /*+ gather_plan_statistics */ count(*) from t1 where c1 is null

Plan hash value: 4294799605

----------------------------------------------------------------------------
| Id  | Operation           | Name | Starts | E-Rows | A-Rows |   A-Time   |
----------------------------------------------------------------------------
|   0 | SELECT STATEMENT    |      |      1 |        |      1 |00:00:00.01 |
|   1 |  SORT AGGREGATE     |      |      1 |      1 |      1 |00:00:00.01 |
|*  2 |   FILTER            |      |      1 |        |      0 |00:00:00.01 |
|   3 |    TABLE ACCESS FULL| T1   |      0 |      1 |      0 |00:00:00.01 |
----------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter(NULL IS NOT NULL)

Note
-----
   - dynamic sampling used for this statement


Returns 0 rows, the table was not accessed at all (Starts = 0 on Operation Id 3), because of the FILTER on Operation Id 2: NULL IS NOT NULL, which obviously to FALSE.

If you use NVL(col, 'N') instead of col, then the database is not able to use this kind of optimization, will access the table and return the correct result:

SQL&gt; select /*+ gather_plan_statistics */ nvl(c1, 'N'), count(*) from t1 group by nvl(c1, 'N');

NVL(C1,'N')            COUNT(*)
-------------------- ----------
N                             1

SQL&gt; select * from table(dbms_xplan.display_cursor(null, null, 'allstats last'));

PLAN_TABLE_OUTPUT
----------------------------------------------------------------------------------------------------------------
SQL_ID  0zfyk18knxtfk, child number 0
-------------------------------------
select /*+ gather_plan_statistics */ nvl(c1, 'N'), count(*) from t1 group by nvl(c1, 'N')

Plan hash value: 136660032

----------------------------------------------------------------------------------------------------------------
| Id  | Operation          | Name | Starts | E-Rows | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
----------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |      1 |        |      1 |00:00:00.01 |       3 |       |       |          |
|   1 |  HASH GROUP BY     |      |      1 |      1 |      1 |00:00:00.01 |       3 |  1156K|  1156K|  323K (0)|
|   2 |   TABLE ACCESS FULL| T1   |      1 |      1 |      1 |00:00:00.01 |       3 |       |       |          |
----------------------------------------------------------------------------------------------------------------

Note
-----
   - dynamic sampling used for this statement


No FILTER this time, and the table was accessed (Starts 1 on Operation Id 2 - TABLE ACCESS FULL).

There was a bug in 10g that caused wrong results with the optimization for CHECK constraints with NULL on transitive predicates:

Bug 5462687 - CHECK constraint can cause wrong results (Doc ID 5462687.8)

This will not help me, because I corrupted the dictionary myself. But if your actual query is more complex than you posted (otherwise do not bother with this), and have transitive predicates, you could try the workaround written in this, and disable this behaviour by setting event 10195

$ oerr ora 10195
10195, 00000, "CBO don't use check constraints for transitive predicates"
// *Cause:
// *Action:


Example:

alter session set event '10195 trace name context level 1';


I do not think this caused by how data is stored, rather just something about the constraints.