This may sound weird but I fixed the issue by doing the following:
Create a new page called "Test Search Input"
Added a "Search Input" module to this newly created page
Typed a search phrase that I knew should bring back results and hit Go
The search then took 10-12 seconds to process/redirect but when it finally redirected, it redirected me to the correct/original Search Results page that had the original Search Results module. I then tested the Search box that is on top of every page and now that too finally redirects to the proper Search Results page too! This is very strange to say the least. It is almost as if some type of caching was going on until I added a new "Search Input" module and forced the application code to not use a cached tabID --> as I understand the Search.ascx.vb uses the following lines to find the tabID
SearchModule As ModuleInfo = objModules.GetModuleByDefinition(PortalSettings.PortalId, "Search Results")
So this was somehow being cached....that is my guess as I believe someone at some point in time had put or moved a "Search Results" on this user created page which it kept redirecting to. Thanks Sebastian and Peter for your help.
searchTabId = SearchModule.TabID
Dim