I don't believe the Reds should entertain trading an inexpensive Bailey for a soon to be expensive Willis. However, I believe a Votto and Cueto for Willis and Lindstrom trade is much more logical.
I believe the Reds should trade any easily replaceable offensive strength, inexpensive or not, for pitching depth. The Reds have proven they can plug in retreads like Aurilia, Hatteberg, Randa, et al, but they have not found the formula for finding pitching depth.
I remember the mid-1970's and the Red Sox parlaying Ted Cox's hot September call-up into a trade for future Hall of Famer, future 20 game winner, and funky delivery guy Dennis Eckersley. Whatever happened to Cox anyway?
Personally, I'd do the trade. Votto may be a future all-star, but Willis and Lindstrum would give the Reds pitching depth. First basemen are much, much more easily developed and/or traded for than 1-3 starters plus bullpen depth.