How to find a datasheet for a part that doesn't exist on the manufacturer's website?
You've pretty much got the process down. 

Recognize that some parts, such as mask-programmed microcontrollers and perhaps some pre-programmed flash microcontrollers may be house numbered, which means they have a part number assigned by the customer, not the manufacturer, and no information will be forthcoming from the latter, nor will you likely ever find a datasheet. The part may or may not be basically a standard part. 

Sometimes, especially with microcontrollers, you can match the package, manufacturer (if known) and the pin pattern (things like power pins, crystal pins, etc.) to reduce the number of options, but it's not an especially rewarding exercise unless you're being paid to analyze someone else's product. The magic is all in the firmware in such cases, and it will be copyright (as well as hardware locked, though that doesn't slow down some unethical folks much).