Please check your version again (probably NOT 5.1.4 since that is very old :)
This is a problem with TO_DAYS, which return NULL for dates like '2009-02-31'.
So it has to search the partition where the NULL's are.
What you can do to minimize the impact of this is to create a partition where the NULL's will be, like 'partition pNULL values less than (0)'
This was changed in:
http://bugs.mysql.com/bug.php?id=20577
entry:
[20 Aug 13:47] Mattias Jonsson
When fixing this bug it will also change the pruning a bit:
For range partitioning, it must also include the first partition (holding the NULL
values) for queries using range search (i.e. <, >, <=, >=, BETWEEN) to be able to find
'virtual' dates like '2000-00-00'.
This can affect performance for range partitioned tables on TO_DAYS() that have a large
first partition. Work around is to create a first partition with VALUES LESS THAN (0).