NameNotFoundException means that the name you used in the lookup is not found in JNDI. Not Bound is used because to put something in jndi, you bind or rebind it. The things to look for are that you are using the same name to do the lookup as you specified in your deployment. Most likely, you will have created an app-server specific file that contains the jndi name. For example in jboss you would have a <jndi-name> element. So if you called it "ejb/XYZ" in your deployment but did a lookup of "myejb/XYZ" then you would get the NameNotFoundException.
It is also possible that you are using references. In which case your lookup would look like: java:comp/env/xxxxx. If that is the case, then you would need to have an <ejb-ref> in your ejb-jar.xml whose ejb-ref-name would be xxxxx. If you are refering to a bean within the same jar, that is all you would need, otherwise you might also need an entry in you app server specific deployment file to resolve the ejb-ref-name to the "real" jndi name.
So, as you can see, without seeing the actual ejb-jar.xml, the app specific file and what you are looking up, it might be hard to say exactly what is wrong.