I don't think there's an actual "easy" way to deal with such different date formats.
If you have the option to nail a "standard date format" to the server that would be the easy way.
A common approach is to build a DateParser for every 'freaky' date format that you have to deal with. Here's an example for your first date, using Joda Time:
String date1 = "16 May 2013 19:27:12 CEST";
DateTimeFormatter fmt = new DateTimeFormatterBuilder()
.appendDayOfMonth(2)
.appendLiteral(' ')
.appendMonthOfYearShortText()
.appendLiteral(' ')
.appendYear(4, 4)
.appendLiteral(' ')
.appendHourOfDay(2)
.appendLiteral(":")
.appendMinuteOfDay(2)
.appendLiteral(":")
.appendSecondOfDay(2)
.appendLiteral(' ')
.appendLiteral("CEST")
.toFormatter();
DateTime parseDateTime = fmt.parseDateTime(date1);
System.out.println(parseDateTime);
I hope this will help you build DateParsers for the other cases. And remember - always save your dates in relation to UTC!