I did find my Birkenstocks to be some of the most comfortable sandals I had owned, after breaking them in of course. What was interesting was that if you didn't wear them pretty much non-stop for a couple of months in warm weather, the soles wouldn't do the whole re-mold themselves to the shape of your foot thing.
These days I've replaced them with a pair of Chacos which are just as comfortable and I can throw them in the washing machine if they get too dirty.