Our server was recently moved and rebuilt (and that's when the issue began).
The search does find products, but only those that have been created (or been enabled) before the transfer. When I search in a category in the catalog, I can find the newly created/uploaded product. It just cannot seem to be accessed by Search.
We are using Magento 1.8.1 and the SPHINX extension (supported by mirasvit).
After backing up our server from a previous date, I was able to locate and eliminate the issue. It was regarding the cache that was created from the product, and it was being misplaced. Took hours of searching, but everything is working beautifully now. =)
Thank you all for trying to help.