First of all, what you say is not true. Using the
fullpage package does not change
\paperwidth/height. It does therefore not change the paper size from A4 to letter. In fact, it computes and sets the margins as well as
\textwidth/height depending on the values of
\paperwidth/height. By default, fullpage will set the left and right margin to 1in. So text should appear horizontally centered on the page.
Now the MiKTeX's setting for the default page size apparently controls the value of
\pdfpagewidth/height in pdflatex. These control the page size that is written into the PDF. Maybe, it affects dvips too, but I did not test it. Also, MiKTeX does not change the default for
\paperwidth/height, meaning that the documentclass or packages like fullpage.sty will configure your margins thinking that the page has letter format, while the PDF may actually have A4 pages. The result is that your document looks bad, really bad, as the text is not centered at all horizontally on the page.
Take a look at the PDF generated by the following code when MiKTeX 2.9 is set to A4 default page size:
Looking at the PDF, the visible margin on the left is visibly wider than the right margin. Also observe how inconsistent the values are.
I conclude that MiKTeX is broken and that the default page size setting should be set to letter size at all times, since the MiKTeX programmer didn't bother to patch the documentclasses and other packages such that \paperwidth/height would be set to A4 (or something else) either, and not just \pdfpagewidth/height.
The obvious workaround is to use the geometry package or koma-script's pagesize options to make the values of \pdfpagewidth/height and \paperwidth/height consistent.