Well I haven't fixed this problem, but I did find a hack around to make things work.
After lots of playing around, I noticed:
http://thatcostumegirl.com/?s=dog doesn't work but
http://thatcostumegirl.com/page/1?s=dog DOES work for some reason.
So I just added /page/1 to the searchform code, so now it reads:
action="<?php bloginfo('url'); ?>/page/1"
And it works! Good enough for me. But I still have no idea what caused the problem in the first place. My best guess at that when she refers to the Dragon Con convention as D*C, somewhere that asterisk broke something. Though I tried adding asterisks to different letters in the title, body and tags, I was unable to break another letter and repeat the original problem. But hey, at least searching works.