If you're interested in wild speculation (I have no idea how Twitter's database works), here's how I interpreted Biz's explanation:
With the new system, say user Foo writes "@Bar lol me too!". Then Twitter can take Foo's follower list, join it with Bar's follower list, and send the message to everyone in the resulting list. Relational databases are very good at joins.
On the other hand, with the old system, they'd have to do a deep inspection of the record for each of Foo's followers to know if they should send the message to that follower. Relational databases are much less good at this.
But, as you and others have pointed out, if the number of users that use the "all @-replies" feature is really so small, it would be fairly inexpensive to cache the list of all of Foo's followers who use that feature, and join them in as well. I don't know why they don't do that -- maybe it adds up (like, if only 3% of users use the feature, but those users follow a lot of other users, they'll each end up in a lot of other users' caches).
With the new system, say user Foo writes "@Bar lol me too!". Then Twitter can take Foo's follower list, join it with Bar's follower list, and send the message to everyone in the resulting list. Relational databases are very good at joins.
On the other hand, with the old system, they'd have to do a deep inspection of the record for each of Foo's followers to know if they should send the message to that follower. Relational databases are much less good at this.
But, as you and others have pointed out, if the number of users that use the "all @-replies" feature is really so small, it would be fairly inexpensive to cache the list of all of Foo's followers who use that feature, and join them in as well. I don't know why they don't do that -- maybe it adds up (like, if only 3% of users use the feature, but those users follow a lot of other users, they'll each end up in a lot of other users' caches).