Separately formatting date elements

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 of the_date()). To repeat the date for posts published
under the same day, you should use the Template Tag the_time() or
get_the_date() (since 3.0) with a date-specific format string.