confusting results from pg_database_size

As part of an testing an archive solution I've updated and deleted 3 or 4
million rows in different tables. I wanted to see how much this shrunk the
database size by running, so I ran a VACUUM FULL FREEZE ANALYZE on both
databases - this took a long time, which is ok considering the number of
rows I updated/deleted

To get the db size I ran the following:

SELECT pg_size_pretty(pg_database_size('deleted_rows_db')),
pg_size_pretty(pg_database_size('original_db'));

Obviously you'd expect the database that is minus 3 million rows to be
smaller, however it was 300Mb larger. (This is a test environment where no
one else has access to the database, both databases were restored from the
same backup. Running a count on the tables shows the rows have definitely
been deleted. - This is the second time I've done this as I considered that
I must have done something wrong the first time).

Does anyone know why the database with fewer rows is larger? how I can find
the real size?, or do something to the database to lose this bloat? (It is
as if the vacuum didn't work - though it appeared to).

Thanks in advance.

-Dan Shoubridge