Are you using managed or unmanaged code?  From my understanding (and I could be wrong about this part, so please feel free to correct me) if you are using managed code, your form will need to be digitally signed so it can be fully trusted.  Without full trust, you may not be able to delete the file.

We are currently using unmanaged code to delete a form from the library and it works fine with the form security set to "Automatically determine security level..." which is translating into Domain level security when we publish the form.

Here's the snippet of jscript code, in case it helps..

==============================
// create an xmlhttp object.
var oXmlHttp = new ActiveXObject("MSXML2.XMLHTTP");

// does the file already exist - returns 200/201 if found, 404 if not
oXmlHttp.Open("HEAD", libraryUrl, false);
oXmlHttp.Send();

// document already exists, delete it
if (oXmlHttp.Status == 200 || oXmlHttp.Status == 201)
{
      oXmlHttp.Open("DELETE", libraryUrl, false);
      oXmlHttp.Send();
}
==============================

Of course, you will probably want to wrap this in a try, catch..