Thanks for putting together a simple example of the problem - it really makes investigating this much easier!
Is there a solution to this problem?
Yes, it turns out there is! My initial guess, by just looking at the image you attached, was that there is some strange clipping/snapping going on. After ruling out the antialiasing possibility (by flicking the switch that you provided) my only other avenue of testing was to set the "snap" keyword to false (for the very limited docs on the snap method see http://matplotlib.org/api/artist_api.html#matplotlib.artist.Artist.set_snap).
Setting the snap does the trick and you end up with the expected results:
import matplotlib.pyplot as plt
import matplotlib.patches as patches
ax = plt.axes()
for x in range(-10,11):
for y in range(-10,11):
rect = patches.Rectangle((x, y), width=0.1, height=0.1,
color='k', snap=False)
ax.add_patch(rect)
plt.xlim([-30, 30])
plt.ylim([-30, 30])
plt.show()
A visual comparison (probably best opening the image in a new window as your browser will probably scale the image and introduce further visual effects):

I'm not particularly knowledgeable about the snap property in mpl and whether this is really desirable behaviour, so I will post a question on the mpl-devel mailing list to open up a conversation about this question. Hopefully this answer will help you in the meantime.
plt.save("a.pdf")the resulting pdf does not suffer from the same artifacts.ec='none'might help a little:rect = patches.Rectangle((x, y), width=1, height=1, color='k',ec='none')