If you are lucky it is merely invisible, and you'll either have to manually enter the full set of configuration strings on the host side, or use some magic keypress incantations to make it visible for pairing. In either case you'll have to check the manual to make any progress.

(edit) In your case it turned out that removing the battery switched it to searchable/pairable state - remember that for the future, it will probably need new pairing whenever it runs out of power!

If you are unlucky, it lacks the regular SPP (serial) profile and pretends to be something else - some early or cheap devices work that way, being built from some cheaper or more easily obtainable, but irregular chipset and fixing that issue at driver level...

I have ran out of battery previously several times. But os2007 had no problem reconnecting without my interaction... Oh well, as long as it works

So does anybody know other BT devices with non-numeric passwords?
If there is only this one device that was released over five years ago Nokia is not very keen on changing their code.