It appears that the WP_Query was correct. I am hosting with WP_Engine and I had to contact their support desk and have the ticket elevated to resolve the issue. Apparently the query, even with the 'orderby' => 'rand', was being cached by their servers. I should have contacted them earlier, but I thought it was something that I was doing incorrectly in my query. Thanks all for the help!
