My thought to fix this is this:

1) Don't allow account to send friend requests for the first 72 hrs of the account but allow them to accept them.
This allows new players to still find and hook-up with their ingame friends but helps keep players from getting spammed by gil sellers.

2) Auto-clean my black list. If a player/character/account is deleted, automatically remove it from my black list.
Hopefully the first option will keep a blacklist from becoming full but this option should help.