Depending on the platform, you might need to right-click on the Firefox browser address bar and choose the "Add search engine" option from the dropdown (where a website has it). Do you see an option to add a new search engine when you right-click the browser address bar at all?
[Edit: just saw the edit that you found it - thanks again for looking around for it too!]
[Edit: just saw the edit that you found it - thanks again for looking around for it too!]