Cover a Region with Rectangles
Python - 272 261 258 251 224

I think I can golf this more. I'm pretty sure this works, but I haven't finished testing it on all of the test cases yet. I finished testing it. It works for all of the test cases.

a=sorted(input())
b=[]
r=range
for i in a:
 c=set(a)-set(b);w=h=1;x,y=i
 if i in b:continue
 while not{(x,y+h)}-c:h+=1
 while all((x+w,y+j)in c for j in r(h)):w+=1
 for j in r(w):
  for k in r(h):b+=(j+x,k+y),
 print x,y,w,h


I'm working on adding images of the results.
Edit: Here are the results from the example and the test cases:







I'm trying to write this in Perl, but I can't figure out how to get multidimensional arrays from stdin without a huge number of characters. Does anyone have any suggestions?