Using db_query and joins
Some thing you can try doing is try printing the entire query string like,

$query = "DELETE a FROM {term_node} a LEFT JOIN {term_data} b ON a.tid = b.tid WHERE a.nid = ".$nid." AND b.vid = ".$vid;
print $query; //printing the query


Notice that I have used the variables instead of place holders %d. This might not be relevant but has helped me many times while debugging queries.

On the link you mentioned http://drupal.org/node/1079620, have you tried #5 ? if not give that a try, it should work IMO.