Yikes! All these workarounds have led me to the conclusion that the HTML checkbox kinda sucks if you want to style it.

As a forewarning, this isn't a css implementation. I just thought I'd share the workaround I came up with in case anyone else might find it useful.

<hr>

I used the HTML5 `canvas` element. 

The upside to this is that you don't have to use external images and can probably save some bandwidth. 

The downside is that if a browser for some reason can't render it correctly, then there's no fallback.

[Working Demo](http://jsfiddle.net/txsFA/)

First, set up a canvas

 var canvas = document.createElement('canvas'),
 ctx = canvas.getContext('2d'),
 checked = 0; // The state of the checkbox
 canvas.width = canvas.height = 15; // Set the width and height of the canvas
 document.body.appendChild(canvas);
 document.body.appendChild(document.createTextNode(' Togglable Option'));

Next, devise a way to have the canvas update itself.

 (function loop(){
 // Draws a border
 ctx.fillStyle = '#ccc';
 ctx.fillRect(0,0,15,15);
 ctx.fillStyle = '#fff';
 ctx.fillRect(1,1,13,13);
 // Fills in canvas if checked
 if(checked){
 ctx.fillStyle = '#000';
 ctx.fillRect(2,2,11,11);
 }
 setTimeout(loop,1000/10); // refresh 10 times per second
 })();

The last part is to make it interactive. Luckily, it's pretty simple:

 canvas.onclick = function(){
 checked = !checked;
 }

This is where you might have problems in IE, due to their weird event handling model in javascript.

<hr>

I hope this helps someone, it definitely suited my needs.