I use this code to delete a messege from my email:
mail.store(id, '+FLAGS', '\\Deleted')
You are mixing 'message sequence numbers' (MSN, what you are calling 'fake ids') and 'unique ids' (UID, which you are calling 'real ids').
It is more convenient to use UIDs everywhere. There are a few commands that come in both MSN and UID versions: FETCH vs UID FETCH, SEARCH vs UID SEARCH, STORE vs UID STORE. You must be consistent, but they otherwise work identically.
So, if you use UID SEARCH, you should use UID STORE:
email.uid('STORE', id, '+FLAGS', '(\\Deleted)') email.expunge()
Regarding deletion on Gmail, specifically: despite the user setting about deletion, I have found it always just removes the 'Inbox' label (or whatever folder you happen to be in), which will leave it Archived in your All Mail folder or equivalent. To really delete it, you may need to:
(UID) MOVE, or a combination of a
(UID) COPYand a deletion.