Yeah, without sample data it's hard to give advice. But the correct way to remove an element from a hash is with delete, not by assigning an empty string. And you're doing something really weird with @lines; if you get to line 100,000 it's going to allocate a 100,000 element array. Considering it's probably sparse you should use a hash for that as well.
If you're still running into memory issues you might look at using a tied hash (DB_File or BerkeleyDB) or even DBD::SQLite to store stuff you've seen somewhere easily retrieved. Those wouldn't keep much of anything in memory but fetching to see the state of a given address should still be pretty quick.