PSTricks works by creating PostScript code which will be embedded in \special{...}
sections in the DVI, and then integrated into the PostScript output by some "driver", e.g. by a program which converts DVI to PS. Later another program can interpret this generated PostScript document when converting it to PDF or some other format. (PostScript is a programming language used in printers, but also implemented in some programs which run on a normal computer, like most programs which convert PostScript files to other formats.)
(Some DVI previewers also understand some PSTricks specials.)
If we don't generate PS, but generate PDF directly, there is no way of embedding PSTricks code in it. Several tools like auto-pst-pdf
make some workarounds, by first creating a DVI containing the PSTricks-related parts of the document, converting this to PS (thereby integrating the PSTricks code) and then converting the PS to PDF for embedding (as images) into the final PDF output.
Of course, this has the usual problems of using images, like what you mentioned. This also only works for PSTricks sections which are clearly separable from the main contents, as you have seen with your label example.
It does not work together with other image formats supported directly by PDFTeX, since these can't be embedded in the normal LaTeX-DVI-PS way.
For the original question (why does PDFLaTeX not support embedding EPS):
The main reason that PDFTeX supports some image formats directly (JPEG, PNG) is that these can in fact be included directly as objects in the PDF format, without any conversion being necessary. Similar rules apply for PDF files (which will be a bit converted, of course).
For EPS, this is not possible.
Of course, one can automatically call some conversion program (and from the comments, this seems to be done with TeXLive 2010/2011), but this will not give any better results than converting them by manually calling the same tool.