That got me curious, so I fired up some old versions of Mozilla Phoenix and checked that out. Turns out already Mozilla Phoenix 0.2 (https://ftp.mozilla.org/pub/phoenix/releases/0.2/), released on October 1, 2002, which was the version which originally introduced the search bar, offered the ability to select different search providers.