Вероятно, у вас должен быть упорядоченный список форматов, которые нужно попробовать (в идеале, используя Joda Time как гораздо лучший API, чем встроенный), и пробуйте каждый по очереди, пока не сработает один. Он не идеален с точки зрения производительности (все исключения для сбоя), но он будет работать и должен быть достаточно понятным.
Конечно, если вы можете связаться с поставщиком веб-услуг и предложить вместо этого вернуть стандартный формат, это будет чище ...