If this is a single-user program, one way you could handle the delete is to rename the file containing your addresses (addybase.adb) to something else (say, addybase.old), then open it for read, dumping all but those you are wishing to delete back to addybase.adb. (This also saves having to read all of the addresses into memory at the same time.)
Later on, you might also want to look at tie or some of the Tie::* modules on CPAN, or the perl DBI, for easier ways to handle the address. Some of the examples I have seen for tie seem to treat the file access similar to a hash, making it easy to reach an entry quickly. Likewise, using the perl DBI with a database and SQL statements also makes access fairly easy.
Hope that helps somewhat.