This might be too manipulative, but what if...
(a) each competition entry takes the form of some online content (written, photo, video, doesn't matter - whatever's appropriate to your business),
(b) each entry has to be verified by your own bot, so each entrant has to cut and paste code for a banner saying "I've just entered the £3K giveaway on blah.com" which has the unique tracking ID for your bot AND a nice link around it. Don't try to optimise for anchor text, just blast your PR into orbit with thousands of 'natural' links popping up everywhere.
The entries can be posted on their blog, homepage etc.