I believe all the info you need is in the PHP Manual for Date/Time. Also, it is recommended that you use get_the_date(); instead of the_date();
Get them month in 3 cap letters?
M is the right format character that outputs a short textual representation of a month (3 chars). Why can’t you use CSS to capitalize all the three letters? I mean, text-transform: uppercase; should do it.
Get only 2 last digits of year?
Use the small y. It outputs two digit representation of a year.
EDIT (to answer the updated question)
The function reference for the_date(); in codex has a special note that says:
When there are multiple posts on a page published under the SAME DAY,
the_date()only displays the date for the first post (that is, the
first instance ofthe_date()). To repeat the date for posts published
under the same day, you should use the Template Tagthe_time()or
get_the_date()(since 3.0) with a date-specific format string.