MySQL column defined with NOT NULL is allowing nulls
What version of mysql is this?

What mode are you running in?

SELECT @@GLOBAL.SQL_MODE, @@SESSION.SQL_MODE;


(This should be run in the context of your application, just in case it is changing it).

MySQL is documented thus: http://dev.mysql.com/doc/refman/5.0/en/data-type-defaults.html

As of MySQL 5.0.2, if a column definition includes no explicit DEFAULT value, MySQL determines the default value as follows:

If the column can take NULL as a value, the column is defined with an explicit DEFAULT NULL clause. This is the same as before 5.0.2.

If the column cannot take NULL as the value, MySQL defines the column with no explicit DEFAULT clause. For data entry, if an INSERT or REPLACE statement includes no value for
the column, MySQL handles the column according to the SQL mode in effect at the time:

If strict SQL mode is not enabled, MySQL sets the column to the implicit default value for the column data type. 


My own testing fails to duplicate your issue

mysql&gt; CREATE TABLE `my_table` (
    -&gt;   `entry_id` int(11) NOT NULL AUTO_INCREMENT,
    -&gt;   `address` varchar(512) NOT NULL,
    -&gt;   `follow_up_to` int(11) DEFAULT NULL,
    -&gt;   PRIMARY KEY (`entry_id`),
    -&gt;   KEY `follow_up_to` (`follow_up_to`)
    -&gt; ) ENGINE=InnoDB AUTO_INCREMENT=536 DEFAULT CHARSET=latin1;
Query OK, 0 rows affected, 2 warnings (0.16 sec)

mysql&gt; INSERT INTO my_table VALUES (NULL, NULL, NULL);
ERROR 1048 (23000): Column 'address' cannot be null
mysql&gt; INSERT INTO my_table (follow_up_to) VALUES (NULL);
Query OK, 1 row affected, 1 warning (0.10 sec)

mysql&gt; SHOW WARNINGS;
+---------+------+----------------------------------------------+
| Level   | Code | Message                                      |
+---------+------+----------------------------------------------+
| Warning | 1364 | Field 'address' doesn't have a default value |
+---------+------+----------------------------------------------+
1 row in set (0.00 sec)

mysql&gt; SELECT * FROM my_table;
+----------+---------+--------------+
| entry_id | address | follow_up_to |
+----------+---------+--------------+
|      537 |         |         NULL |
+----------+---------+--------------+
1 row in set (0.00 sec)


The fact the old data had nulls shouldn't matter. The Alter table should have 'truncated' the nulls into empty strings

mysql&gt; SHOW CREATE TABLE my_table\G
*************************** 1. row ***************************
       Table: my_table
Create Table: CREATE TABLE `my_table` (
  `entry_id` int(11) NOT NULL AUTO_INCREMENT,
  `address` varchar(512) NOT NULL,
  `follow_up_to` int(11) DEFAULT NULL,
  PRIMARY KEY (`entry_id`),
  KEY `follow_up_to` (`follow_up_to`)
) ENGINE=InnoDB AUTO_INCREMENT=536 DEFAULT CHARSET=latin1
1 row in set (0.04 sec)

mysql&gt; ALTER TABLE my_table MODIFY address VARCHAR(512) NULL DEFAULT NULL;
Query OK, 1 row affected (0.76 sec)
Records: 1  Duplicates: 0  Warnings: 0

mysql&gt; INSERT INTO my_table VALUES (NULL, NULL, NULL), (NULL, NULL, NULL);
Query OK, 2 rows affected (0.05 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql&gt; SELECT * FROM my_table;
+----------+---------+--------------+
| entry_id | address | follow_up_to |
+----------+---------+--------------+
|      535 |         |         NULL |
|      536 | NULL    |         NULL |
|      537 | NULL    |         NULL |
+----------+---------+--------------+
3 rows in set (0.04 sec)

mysql&gt; ALTER TABLE my_table MODIFY address VARCHAR(512) NOT NULL;
Query OK, 3 rows affected, 2 warnings (0.83 sec)
Records: 3  Duplicates: 0  Warnings: 2

mysql&gt; SHOW WARNINGS;
+---------+------+----------------------------------------------+
| Level   | Code | Message                                      |
+---------+------+----------------------------------------------+
| Warning | 1265 | Data truncated for column 'address' at row 2 |
| Warning | 1265 | Data truncated for column 'address' at row 3 |
+---------+------+----------------------------------------------+
2 rows in set (0.04 sec)

mysql&gt; SELECT * FROM my_table;
+----------+---------+--------------+
| entry_id | address | follow_up_to |
+----------+---------+--------------+
|      535 |         |         NULL |
|      536 |         |         NULL |
|      537 |         |         NULL |
+----------+---------+--------------+
3 rows in set (0.04 sec)

mysql&gt; INSERT INTO my_table VALUES (NULL, NULL, NULL), (NULL, NULL, NULL);
Query OK, 2 rows affected, 2 warnings (0.08 sec)
Records: 2  Duplicates: 0  Warnings: 2

mysql&gt; SELECT * FROM my_table;
+----------+---------+--------------+
| entry_id | address | follow_up_to |
+----------+---------+--------------+
|      535 |         |         NULL |
|      536 |         |         NULL |
|      537 |         |         NULL |
|      538 |         |         NULL |
|      539 |         |         NULL |
+----------+---------+--------------+
5 rows in set (0.05 sec)