Тип, возвращаемый фунцкией to_timestamp - не timestamp. :-)

# \dT timestamp
List of data types
Schema | Name | Description
------------+-----------------------------+---------------
pg_catalog | timestamp without time zone | date and time
(1 row)

# \df to_timestamp
List of functions
Result data type | Schema | Name | Argument data types
--------------------------+------------+--------------+---------------------
timestamp with time zone | pg_catalog | to_timestamp | text, text
(1 row)

- а че "timestamp with time zone" ето разве не "timestamp" ???
- Точно так!!!
- а че есть "timestamp" без "time zone" ???
- Точно так!!!

Сделайте
create table xz(i int4,updatetime timestamp with timezone);
или
explain select * from xz where to_timestamp('DD.MM.YYYY','20.04.2003')::timestamp<updatetime;

vacuum analyze сделан?

опечатка: у функции to_timestamp неправильный порядок аргументов.

$ psql -c "create table ttt ( t1 timestamp )"
$ perl -e 'print "begin;\n"; for my $y ( 1901 .. 1966 ) { for my $d ( 1..1234 ) { print "insert into ttt values ( to_timestamp( \x27$y\x27, \x27YYYY\x27 ) );\n" } } print "commit;\n"; ' | psql
$ psql
# create index t1 on ttt ( t1 );
# select count(*) from ttt;
count
-------
81444
(1 row)
# select count(*) from ( select distinct t1 from ttt ) as a;
count
-------
66
(1 row)
# create index t1 on ttt ( t1 );
# explain select * from ttt where to_timestamp('1933','YYYY')::timestamp < t1;
QUERY PLAN
------------------------------------------------------------------------------------------
Seq Scan on ttt (cost=0.00..1825.27 rows=27148 width=8)
Filter: ((to_timestamp('1933'::text, 'YYYY'::text))::timestamp without time zone < t1)
# vacuum analyze ttt;
# explain select * from ttt where to_timestamp('1933','YYYY')::timestamp < t1;
QUERY PLAN
----------------------------------------------------------------------------------------------
Index Scan using t1 on ttt (cost=0.00..712.24 rows=27148 width=8)
Index Cond: ((to_timestamp('1933'::text, 'YYYY'::text))::timestamp without time zone < t1)

P.S.:

# explain analyze select * from ttt where to_timestamp('1965','YYYY')::timestamp < t1;
Total runtime: 5.31 msec
# explain analyze select * from ttt where to_timestamp('1933','YYYY')::timestamp < t1;
Total runtime: 275.59 msec
# explain analyze select * from ttt where to_timestamp('1900','YYYY')::timestamp < t1;
Total runtime: 555.48 msec
# set enable_indexscan to off;
# explain analyze select * from ttt where to_timestamp('1965','YYYY')::timestamp < t1;
Total runtime: 1058.16 msec
# explain analyze select * from ttt where to_timestamp('1933','YYYY')::timestamp < t1;
Total runtime: 1208.25 msec
# explain analyze select * from ttt where to_timestamp('1900','YYYY')::timestamp < t1;
Total runtime: 906.10 msec

Провел ваш тест. Результаты почти такие же как и у вас. Не использует он индекс! :-(

Могу лишь посоветовать поиграться с run-time параметрами CPU_*, DEFAULT_STATISTICS_TARGET. Однако у меня с наскока ничего не получилось.

P.S.: Все-таки исправьте порядок аргументов в to_timestamp.