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!