PostgreSQL CHECK constraint is evaluated wrongly

Following schema allows to violate the CHECK constrait, but only once. Then the constraint is correctly enforced.

drop database if exists example;
create database example;

create table example_table (
    id integer not null,
    value integer not null,
    constraint pk primary key (id));

CREATE OR REPLACE FUNCTION checkunique()
  RETURNS boolean AS
$BODY$
begin
    return NOT Exists (
        Select 1 
        FROM example_table AS a, example_table AS b 
        WHERE a.id != b.id AND a.value = b.value);
end
$BODY$
LANGUAGE plpgsql STABLE;

alter table example_table add constraint unique_value check (checkunique());

The check constraint substitutes UNIQUE constraint because I need to store large VARCHARs in production case and there is a limit on size of indexed cell.

Now data that breaks the CHECK constraint can be inserted:

insert into example_table (id, value) values (0,0);
select checkunique(); -- returns true
insert into example_table (id, value) values (1,0);
select checkunique(); -- returns false

Even the database itself admits that the constraint function evaluates to false, however data are stored.

Now one can't insert any, even constraint satisfying data:

insert into example_table (id, value) values (2,2);
--error output:
--ERROR: new row for relation "example_table" violates check constraint "unique_value"
--SQL state: 23514
--Detail: Failing row contains (2, 2).

How can I make the constraint work correctly?

Environment: PostgreSQL 9.3.6, Fedora 20 x64