I had that case once:
1. Initially I had my printer using Letter size.
- It was printing just fine
- So far so good
2. The company decided to change the size from Letter to A4
3. I configured the printer to default print on A4
4. Cloud Print was remembering Letter size
- I had to change that every time manually
5. I un-linked the printer from Cloud Print
6. I readded the printer
7. Now, Cloud Print was recognizing A4
8. I tried the opposite and indeed, I change my printer back to Letter, but now it was recognizing A4
I think Cloud Print, can't recognize future printer changes and remembers only the initial setup.
I hope that helps!