I have developed an ecommerce site utilizing VF database. And I too had problems and deleting records. I use a DNSLess connection (See example below). Also see the example of adding records. I think your problem is in the recordset locktype (mine seemed to be). I was forced to use native ADO comands. such as rs.LockType = adLockoptimistic did not work where as rs.Locktype = 3 did.

Example DNSles VF Datasource connection string (I put mine in the global.asa in the onApplication Start)...

Sub Application_OnStart
set ConStr = Server.CreateObject("ADODB.Connection")
ConStr = "DRIVER=Microsoft Visual FoxPro Driver;"
ConStr = ConStr & "BackgroundFetch=Yes;"
ConStr = ConStr & "Exclusive=No;"
ConStr = ConStr & "SourceType=DBC;"
theDatabase = server.mappath("\YourRootDirectory\data\inventory.dbc")
ConStr = ConStr & "SourceDB="&theDataBase
Application("connectionString") = ConStr
end Sub

Example of adding records...

'First setup you connection like so if you use the application scheme
Set dbMain = Server.CreateObject("ADODB.Connection")
dbMain.Open Application("connectionString")

'Then add your record

Set rsCustomers = Server.CreateObject("ADODB.Recordset")
CustSQL = "SELECT * FROM customers where 1 <> 1"
'BeginTrans speeds up accesing data 17 times
dbMain.BeginTrans
rsCustomers.ActiveConnection = dbMain
rsCustomers.CursorType = 1
rsCustomers.LockType = 3
rsCustomers.Open CustSQL
rsCustomers.AddNew
rsCustomers( "customerid" ) = CustID
rsCustomers ( "fname" ) = qfname
rsCustomers ( "lname" ) = qlname
rsCustomers ( "address" ) = qaddress
rsCustomers ( "city" ) = qcity
rsCustomers ( "state" ) = qstate
rsCustomers ( "zip" ) = qzip
rsCustomers ( "country" ) = qcountry
rsCustomers ( "phone" ) = qphone
rsCustomers ( "email" ) = qemail
rsCustomers ( "machinemake" ) = qmake
rsCustomers ( "machinemodel" ) = qmodel
rsCustomers ( "freedollars" ) = 0
dbMain.CommitTrans
rsCustomers.Update
rsCustomers.Close

'By the way since VF Database does not use incremental fields I create
'one table with one numeric field for each table.That way I can ensure
'that my indexes are always unique NEVER use session or application variables.
'If the server goes down they will result in duplicate index numbers
'Here is what I do for my customer table...

Set rsindex = Server.CreateObject("ADODB.Recordset")
indexSQL = "SELECT customers FROM Set rsindex = Server.CreateObject("ADODB.Recordset")
indexSQL = "SELECT customers FROM indexes"
rsindex.ActiveConnection = dbMain
rsindex.CursorType = 1
rsindex.LockType = 3
rsindex.Open indexSql
CustID = trim(rsindex("customers"))
CustID = CustID + 1
'Assign a new value to the customer index field
rsindex( "customers" ) = CustID
rsindex.Update
rsIndex.Close"
rsindex.ActiveConnection = dbMain
rsindex.CursorType = 1
rsindex.LockType = 3
rsindex.Open indexSql
CustID = trim(rsindex("customers"))
CustID = CustID + 1
'Write a new index value to the customer field
rsindex( "customers" ) = CustID
rsindex.Update
rsIndex.Close

Hope this helps
Good luck!
Mike Cox