I hated my Shimano sandals. I got hot foot, and my feet stunk. Thick insoles helped, but didn't eliminate the problems. Thick wool socks helped, but why wear sandals if you have to wear thick wool socks?
On a 2002 St. Charles, MO to Seaside, OR trip (Lewis & Clark Trail) another rider wore bike sandals. At the start he swore that they were the only comfortable bike shoes he'd ever had. He complained of hot foot and stopped a few times because his feet hurt.
On a 2003 cross country trip, three other riders showed up with bike sandals, one wore them for the whole trip, but with heavy wool socks, which he often took off in the late afternoon. The two other riders wore bike sandals once early in the trip, but I never saw the bike sandals again.
The other people I know that wear bike sandals also wear thick wool socks.
My advice would be to test them thoroughly before commiting to them for a long ride. That goes for any shoe you take!
I would also avoid shoelaces. They can easily get caught between your chain and chainwheel. You might be able to backpedal to get them out, but if you don't realize what's happening in time, a nasty crash could result! I no longer wear shoes with laces when I ride my bike. If you do, be sure to tie them securely so that they cannot come loose and catch in the chain.
My last pair of shoes, Specialized Body Geometry, hurt my right knee until I switched to Superfeet gray insoles
http://www.superfeet.com/content/grey.html . I wore the shoes and insoles for two cross country tours. So, consider different innersoles. If possible, try the innersoles before buying, because most of them are thicker than bike shoe innersoles, and you might not be able to get your foot in the shoe. The Superfeet grays are very thin, but they worked great for me.
The Specialized shoes are very worn. As soon as the weather improves, I've got a pair of Sidi Dominators ready to go. I found them on the clearance pile at REI, $85 vs. $210. The only thing I can detect wrong with them is a very tiny squeak when I walk, so I guess I'll have to just ride.