Chai expected [Function] to throw an (error) not passing the test on Node

The question:

I'm using Chai to do the tests and I seem to be stuck on testing an expected error:

"*Chai expected [Function] to throw an (error) *"

Current code:

Here's the code of the test:

describe('Do something', function () {

    it('should remove a record from the table', function (done) {

        storage.delete(ID, done);

    });

    it('should throw an error when the lookup fails', function () {

         expect(storage.delete.bind(storage, ID)).to.throw('Record not found');
    });
});

Here's the code of the function:

delete: function (id, callback) {
    //  Generate a Visitor object
    visitor = new Visitor(id);

    /*  Delete the visitor that matches the queue an
        cookie provided. */
    tableService.deleteEntity(function (error, response) {

        //  If successful, go on.
        if (!error) {
            // Do something on success.
        }
        //  If unsuccessful, log error.
        else {
            if (error.code === 'ResourceNotFound') {
                throw new Error('Record not found');
            }

            //  For unexpected errros.
            else {

                throw new Error('Table service error (delete): ' + error);

            }
        }
        if (callback) callback();
    });

},

Attempted solutions:

I've tried multiple variations of calling expect function (including calling anonymous function:

expect(function() {storage.delete(ID);}).to.throw('Record not found');

Bind, as provided in the example,

and the basic one of

expect(storage.delete(ID)).to.throw('Record not found');

I've also tried substituting the throw parameter from 'Record not found' to multiple things including directing the input to an already created error (Error), and creating a new error in the parameter (new Error('Record not found'));

Possible causes:

I have a suspicion that the error is not being thrown because it takes a while for the test to communicate with the database to delete the record, however I am not sure of how I could remedy that.