I tried rebuilding the search index and that didn't fix the problem. I tried doing it again and checking the "delete index" option and that didn't fix it either. One thing I noticed though is that when I tried to rebuild the search it starts from post 216.023 , I'm not sure if that means anything?
Edit: these searches that come up empty are the ones that include 2-letter and 3-letter words (but they also include larger words). Before changing my table to innodb this was working. For example searchin for "Pirates of the Caribbean" was returning results before, but now returns zero results.