Indeed all my comments throughout this thread have been based on your statement that you provide no child supoort, just food & shelter 4 months/year. I would suggest reading pages 18 and 19 of Pub 501, which has a more in-depth discussion of how to determine the cost of upkeep. See:
http://www.irs.gov/pub/irs-pdf/p501.pdf
Upkeep includes food, lodging, clothing, education, medical & dental, recreation, transportation, and similar necessities. Note that the value of lodging is determined by the fair market value of the room provided for the child - in other words, even though your ex has no mortgage there is a value to the room she provides, and that value is most likely related to the value of her home.
As I read it the tie breaker applies only to breaking ties for two people who can both claim a child as a "qualifying child." But neither you nor the grandparents can do that - the question is whether the children are your "qualifying relatives," not "qualifying children," and there is a big difference. I don't see any tie breaker rules for qualifying children. So it boils down to doing the calculation of (a) the upkeep you provided divided by (b) the total upkeep provided by all parties throughout the year. If that number is greater than 50% then by al means go ahead and claim the children. But be sure to keep notes of yuor calculations so that if you are audited in 2-3 years you can justify your filing.