For the main Straight Dope page (www.straightdope.com), the “It’s taking longer than we thought” tag is on the earliest copy that the Wayback Machine has, which is December 30, 1996. So it’s been there apparently since the beginning, or at least very close to the beginning.
The tag is on the main page, but is not on the message board (boards.straightdope.com) for any wayback copies archived in 2004 or earlier, but it is on the message board copies from 2006 and later. Unfortunately there aren’t any wayback captures in between them. So, it was added to the SDMB sometime between January 1, 2004 and April 6, 2006.
I don’t see that tag line in any of the books (I only looked on the front and back covers and the first few and last few pages).
ISTR that line being used in the column at one point, before this message board was in existence. I’ll have to search the books and see if it’s there somewhere.
I got my first edition of the first Straight Dope book out, Copyright 1984. OMG, that thing’s over 400 pages! And the print didn’t seem that small the first dozen times I read it! What happened?
Needless to say, I’ve not perused all of it yet in my search for the phrase. But it didn’t appear in little Ed’s introduction. I will persevere.