Why won't my DML statement use partition pruning?

I had a case today where a developer issued a DELETE statement against a 600 mill row table.
The table is RANGE PARTITIONED, with partitions per month. The table is created with parallel degree 8.

The DML statement looked correct, and was using the partition key in the predicate:

delete 
from  mytable 
where val_date = to_date('31.10.2013','DD.MM.YYYY');

The execution plan looked as follows:

---------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation             | Name       | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |    TQ  |IN-OUT| PQ Distrib |
---------------------------------------------------------------------------------------------------------------------------------
|   0 | DELETE STATEMENT      |            |   611K|    16M|  5597   (2)| 00:01:08 |       |       |        |      |            |
|   1 |  DELETE               | MYTABLE    |       |       |            |          |       |       |        |      |            |
|   2 |   PX COORDINATOR      |            |       |       |            |          |       |       |        |      |            |
|   3 |    PX SEND QC (RANDOM)| :TQ10000   |   611K|    16M|  5597   (2)| 00:01:08 |       |       |  Q1,00 | P->S | QC (RAND)  |
|   4 |     PX BLOCK ITERATOR |            |   611K|    16M|  5597   (2)| 00:01:08 |   118 |   118 |  Q1,00 | PCWC |            |
|*  5 |      TABLE ACCESS FULL| MYTABLE    |   611K|    16M|  5597   (2)| 00:01:08 |   118 |   118 |  Q1,00 | PCWP |            |
---------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
5 - filter("VAL_DATE"=TO_DATE(' 2013-10-31 00:00:00', 'syyyy-mm-dd hh24:mi:ss'))

It looks like oracle is ignoring the predicate and performs a full table scan.
True or not?
When explaining without parallel slaves:

explain plan for 
delete /*+ no_parallel (a) */ 
from mytable a
where val_date = to_date('31.10.2013','DD.MM.YYYY');
select * from table(dbms_xplan.display);

Then the execution plan is revealed as follows:

------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name       | Rows  | Bytes | Cost (%CPU)| Time     | Pstart| Pstop |
------------------------------------------------------------------------------------------------------
|   0 | DELETE STATEMENT        |            |   611K|    16M| 40443   (2)| 00:08:06 |       |       |
|   1 |  DELETE                 | MYTABLE    |       |       |            |          |       |       |
|   2 |   PARTITION RANGE SINGLE|            |   611K|    16M| 40443   (2)| 00:08:06 |   118 |   118 |
|*  3 |    TABLE ACCESS FULL    | MYTABLE    |   611K|    16M| 40443   (2)| 00:08:06 |   118 |   118 |
-----------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
3 - filter("VAL_DATE"=TO_DATE(' 2013-10-31 00:00:00', 'syyyy-mm-dd hh24:mi:ss'))

Note that when you use the NO_PARALLEL hint, you need to reference the table by an alias, in my case "a". The statement below

delete /*+ no_parallel */ 
from mytable...

will not, to my surprise, override the parallel settings, while

delete /*+ no_parallel (a)*/ 
from mytable a...

will.

In conclusion, simulating a non-parallel execution revealed that the query was indeed using partition pruning (as can be seen from line 2 above that reads "PARTITION RANGE SINGLE"). In the original explained plan, this is not pointed out by oracle, and can easily lead you think that oracle is not taking advantage of partitioning.