Firstly, I'm not mysql expert, however, below are my guesses:
1) My first guess was, you are using mysql command without password (and you provided password in config file), and that is the reason for 'using password: NO' thing.
2) However, your second command is interesting. It works with full path, but doesn't work with simple command. As of this, my (another) guess is - path defined for mysql in PATH variable is different from actual path (or more than 1 versions of mysql are there etc.).
They are totally 2 different commands, the one in init.d is a script (you can proly check by using cat mysql inside init.d folder) and the mysql(anywhere) on the first one is also different(proly the one in /usr/bin you can check by using which command 'which mysql') . I think the one you need is the 2nd one. the first one is the client app.
subject: [CentOS 5.5] MySQL stop gives access denied error