I wrote "Han hittade tvålen inte", I guess that is wrong, but thereby I saw a suggested translation of "Han hittade ej tvålen" - is ej a synonym of inte?
Yes, ej is synonymous with inte. It's a bit old-fashioned to use, but still used in some expressions and sometimes in formal warnings.
Why is it wrong to put inte at the end of the sentence, after tvål which is the object? Is it the rule that adverbs must follow immediately after the verb they modify?
Adverbs go after the verb in a main clause.
Is it also possible to say: "Han hittade ingen tvål"?
Yes, but it means "He found no soap."
Is there another way to say soap?
Yes, såpa - but that's the kind you use for your floors, not for your hands. :)
Han kunde inte hitta tvålen.
Stämmer det inte?
Sure - but it means "He could not find the soap."