If all you need to do is check if a particular address has ever been used, you need to follow the following procedure:
*generate a set of all addresses that have ever received a transaction
*convert each brainwallet passphrase into a private key (which you will subsequently convert into an address)
*compare each tested address from the above step to the items in your set in step 1

The list of addresses that have ever received a transaction is very large, so you will need to use a hashing algorithm that can handle a sufficiently large number of items, or else your runtime will suffer.

Assuming there are no collisions in your above set, you should be able to compare each tested passphrase in O(1) time.