Simple SQL INSERT to avoid duplication failed: why?

Ok, I tried to be clever and I wrote code to avoid inserting duplicate data.
The calling function has a try-catch to recover from this, but I am curious
as to why it failed:

INSERT INTO

mdx_lib.acache_mdx_logic_address_validation

(

address,

postal_code,

address_id

)

SELECT

'306 station 22 1 2 st' AS address,

'29482' AS postal_code,

100165016 AS address_id

WHERE

NOT EXISTS

( SELECT

1

FROM

mdx_lib.acache_mdx_logic_address_validation

WHERE

address = '306 station 22 1 2 st'

AND postal_code = '29482'

)

Exec status=PGRES_FATAL_ERROR error=ERROR: duplicate key value violates
unique constraint "uq_acache_mdx_logic_address_validation_idx"

DETAIL: Key (address, postal_code)=(306 station 22 1 2 st, 29482) already
exists.

The client insists that this process is the only one running, so if he's
right no other process could be inserting a row with the same data between
the SELECT . NOT EXISTS and the actual INSERT operation.

This particular code works as expected right now (SELECT returns 0 rows,
therefore no rows INSERTed).

Should this have worked?

Carlo