I am pleased to say I think this problem is no more.
I'm working in "blocks" instead of pixels. So I have a db table thats 100x100 block, a 40x40px ad is a 4x4 block.
I have code that loops through vert & horz to check available blocks, if there is any then allocate the blocks with the ad id.
For display I can then take the first vert & horz number for each ad and use that to absolute position the ad on the page.