If I create a DateFormat for the current locale, using
DateFormat.getInstance(), set lenient parsing off, and then try
to parse a date string where the first element of the date
(whatever precedes the first delimiter) is missing, parsing the
string succeeds for some locales - which I think is wrong - and 
throws a ParseException for others - which I think is correct.

The following is a complete program that demonstrates the problem.
For each of the available locales, it creates a DateFormat with
strict parsing; uses that  customer  to format today's date; removes
from the resultant string everything before the first non-numeric
character; and attempts to parse the result of doing that into
a Date.

import java.text.*;
import java.util.*;

public class EmptyFirstElementTest
{
   public static void main(String[] args)
   {
      Locale[] locales = Locale.getAvailableLocales();
      Date date = new Date();
      for (int loc = 0; loc < locales.length; loc++)
      {
         Locale.setDefault(locales[loc]);
         System.out.print(Locale.getDefault());
         System.out.print(" --- ");
         DateFormat df = DateFormat.getDateInstance(DateFormat.SHORT);
         df.setLenient(false);
         String str = df.format(date);
         for (int c = 0; c < str.length(); c++)
         {
            if (!Character.isDigit(str.charAt(c)))
            {
               str = str.substring(c);
               break;
            }
         }
         System.out.print(str);
         System.out.print(" --- ");
         try
         {
            System.out.print(df.parse(str));
         }
         catch(ParseException ex)
         {
            System.out.print(ex);
         }
         System.out.println();
      }
   }
}

For each locale, the output shows: the locale identifier; the
formatted date after removal of the leading numerics; and the
result (a Date or a ParseException) of parsing the mutilated
string.

en --- /13/99 --- Wed Jan 13 00:00:00 GMT+00:00 1999
en_US --- /13/99 --- Wed Jan 13 00:00:00 GMT+00:00 1999
ar --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_AE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_BH --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_DZ --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_EG --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_IQ --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_JO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_KW --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_LB --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_LY --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_MA --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_OM --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_QA --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_SA --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_SD --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_SY --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_TN --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ar_YE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
be --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
be_BY --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
bg --- -1-13 --- java.text.ParseException: Unparseable date: "-1-13"
bg_BG --- -1-13 --- java.text.ParseException: Unparseable date: "-1-13"
ca --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ca_ES --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
cs --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
cs_CZ --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
da --- -01-99 --- java.text.ParseException: Unparseable date: "-01-99"
da_DK --- -01-99 --- java.text.ParseException: Unparseable date: "-01-99"
de --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_AT --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_AT_EURO --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_CH --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_DE --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_DE_EURO --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_LU --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
de_LU_EURO --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
el --- /1/1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
el_GR --- /1/1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_AU --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_CA --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_GB --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_IE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_IE_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_NZ --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
en_ZA --- /01/13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
es --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_AR --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_BO --- -01-99 --- java.text.ParseException: Unparseable date: "-01-99"
es_CL --- -01-99 --- java.text.ParseException: Unparseable date: "-01-99"
es_CO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_CR --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_DO --- /13/99 --- Wed Jan 13 00:00:00 GMT+00:00 1999
es_EC --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_ES --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_ES_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_GT --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_HN --- -13-99 --- java.text.ParseException: Unparseable date: "-13-99"
es_MX --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_NI --- -13-99 --- java.text.ParseException: Unparseable date: "-13-99"
es_PA --- /13/99 --- Wed Jan 13 00:00:00 GMT+00:00 1999
es_PE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_PR --- -13-99 --- java.text.ParseException: Unparseable date: "-13-99"
es_PY --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_SV --- -13-99 --- java.text.ParseException: Unparseable date: "-13-99"
es_UY --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
es_VE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
et --- -1-99 --- java.text.ParseException: Unparseable date: "-1-99"
et_EE --- -1-99 --- java.text.ParseException: Unparseable date: "-1-99"
fi --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fi_FI --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fi_FI_EURO --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_BE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_BE_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_CA --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
fr_CH --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_FR --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_FR_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_LU --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
fr_LU_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
hr --- .01.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
hr_HR --- .01.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
hu --- .01.13. --- Tue Jan 13 00:00:00 GMT+00:00 1970
hu_HU --- .01.13. --- Tue Jan 13 00:00:00 GMT+00:00 1970
is --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
is_IS --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
it --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
it_CH --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
it_IT --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
it_IT_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
iw --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
iw_IL --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ja --- /01/13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
ja_JP --- /01/13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
ko --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
ko_KR --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
lt --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
lt_LT --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
lv --- .13.1 --- Tue Jan 13 00:00:00 GMT+00:00 1970
lv_LV --- .13.1 --- Tue Jan 13 00:00:00 GMT+00:00 1970
mk --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
mk_MK --- .1.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
nl --- -1-99 --- java.text.ParseException: Unparseable date: "-1-99"
nl_BE --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
nl_BE_EURO --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
nl_NL --- -1-99 --- java.text.ParseException: Unparseable date: "-1-99"
nl_NL_EURO --- -1-99 --- java.text.ParseException: Unparseable date: "-1-99"
no --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
no_NO --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
no_NO_NY --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
pl --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
pl_PL --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
pt --- -01-1999 --- java.text.ParseException: Unparseable date: "-01-1999"
pt_BR --- /01/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
pt_PT --- -01-1999 --- java.text.ParseException: Unparseable date: "-01-1999"
pt_PT_EURO --- -01-1999 --- java.text.ParseException: Unparseable date: "-01-1999"
ro --- .01.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ro_RO --- .01.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ru --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
ru_RU --- .01.99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
sh --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sh_YU --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sk --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
sk_SK --- .1.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
sl --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sl_SI --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sq --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
sq_AL --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
sr --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sr_YU --- .1.13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
sv --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
sv_SE --- -01-13 --- java.text.ParseException: Unparseable date: "-01-13"
th --- /1/1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
th_TH --- /1/1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
tr --- .01.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
tr_TR --- .01.1999 --- Fri Jan 01 00:00:00 GMT+00:00 1999
uk --- /1/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
uk_UA --- /1/99 --- Fri Jan 01 00:00:00 GMT+00:00 1999
zh --- -1-13 --- java.text.ParseException: Unparseable date: "-1-13"
zh_CN --- -1-13 --- java.text.ParseException: Unparseable date: "-1-13"
zh_HK --- ?1?13? --- Tue Jan 13 00:00:00 GMT+00:00 1970
zh_TW --- /1/13 --- Tue Jan 13 00:00:00 GMT+00:00 1970
(Review ID: 52567)
======================================================================

Depending on the context, it should normally be possible to
check whether the string to be parsed begins with a digit, and
not to attempt to parse it if it does not. It's not really
satisfactory, though.
======================================================================

The description sounds reasonable. parse() methods should throw ParseException instead.
  xxxxx@xxxxx   1999-09-03

See also 4227284. These are same problem that how strictly pattern should be applied when parse()-ing. As my opinion, even when parsing, the pattern count should have meaning like as format() do. Unless otherwise, we have to document them out.
  xxxxx@xxxxx   1999-10-27

Because of 4322313's fix for Merlin-beta2, this problem becomes not reproduciable.
Now all invalid dates which have been mentioned in this description cause ParseException. 
If a delimiter is '-' like a case of "1999-10-27", an error index which is
returned by ParseException.getErrorOffset() might be different from other cases like "1999/10/27" or "1999.10.27" because '-' is intepreted as a sign character first. 
  xxxxx@xxxxx   2001-07-04

A setLenient(false) DateFormat will also successfully (incorrectly) parse a
string with a 2 digit year where a 4 digit year is specified.
import java.util.*;
import java.text.*;
public class Test {
  public Test() {
  }
  public static void main(String argv[]) {
    String pattern = "MM/dd/yyyy";
    DateFormat df = new SimpleDateFormat(pattern);
    df.setLenient(false);
    Date date = null;
    String s = "01/01/98";
    try {
      date = df.parse(s);
    } catch (ParseException pe) {
      pe.printStackTrace();
      return;
    }
    System.out.println("Pattern: '" + pattern + "' String:
'" + s + "' Formatted Date: '" + df.format(date) +
"'");
    return;
  }
}
The above program should throw a ParseException.
I use DateFormat to validate dates entered into a TextField before sending them
to a DB expecting a four digit date.  This bug means I accept a year  I should
reject, 98, and store it as 0098, when the user thinks they entered 1998.