Just to confirm the steps you have tried, are those as shown in the attached screenshot?
I never have the Search Box on any of my system but went through the steps just to confirm and things worked as described in the article without having to do any of the steps described under "If you still don't see the Search box, try opening taskbar settings."