As shown in the example, "a:visited" completely ignores padding, margin and width declarations. The colour changes, so we can see that the pseudo-class is working, but it's ignoring those 3 declarations. It might be ignoring more declarations, but I didn't have time to extensively try out everything.
This is by design, see <http://dbaron.org/mozilla/visited-privacy>.
I see. But I still can't see why 'padding' and 'margin' would be disabled. You could disable padding/margin querying using Javascript to protect a user's history if you want. The privacy issue is about detection, not about presentation. We should be crippling JS' ability to detect certain things, not CSS' ability to show them.
You can't disable querying layout changes from JavaScript, because they affect layout of other elements, so the difference can be detected indirectly by querying their positions. Besides the link I gave, you can read an 8 year long history of discussions at <https://bugzilla.mozilla.org/show_bug.cgi?id=147777>.