Google Datastore model User and Messages efficently
Your second approach seem to be the best. Having a Message entity with key relations to sender/reciever.

As for you deleting a user dilema, you should consider not removing the entity when a user is deleted as this would break your db consistency. You should probably just have a logic deletion (eg a boolean value changed when a user is deleted), that way, messages sent to/from that user will stll make sense for other users.