I found the solution!
Just as I suspected I needed one more table to be filtered, and that did the whole trick!
So the line that was missing: ii.order_id = wp_posts.ID, and some other tweaks ;)
SELECT COUNT(DISTINCT wp_posts.ID)
FROM wp_posts, wp_postmeta, wp_term_relationships, wp_woocommerce_order_itemmeta oi, wp_woocommerce_order_items ii
WHERE wp_term_relationships.term_taxonomy_id = (xx - order status id)
AND wp_term_relationships.object_id = wp_posts.ID
AND oi.order_item_id = ii.order_item_id
AND oi.meta_key = '_product_id'
AND oi.meta_value = (yy - specific product id, the same id as in wp_posts)
AND ii.order_id = wp_posts.ID
AND wp_postmeta.post_id = wp_term_relationships.object_id
AND wp_posts.post_status = 'publish'
Make sure not to select 'shop_order" post type since it will give wrong result :) and note, that complete status may have few more values, since woocommerce has different state values for completed, removed, paid, and canceled order.
I hope this will be helpful to someone else :)
And many thanks to Kiril for guiding me to this solution!