Any time Unity cannot identify the calling party as a subscriber, the message is left as an outside (unidentified) caller. This is not related to UM vs. VM. You can, of course, always explicitly log into your mailbox before leaving a message but most folks don't do this in a DID type setup.
If you are calling from an unknown number (say your cell phone if you haven't added it as an alternate extension) to someone to leave a message, it's left as an outside caller with the subject as you noted. This can also happen if the phone system does not get us the calling number when the call is forwarded - in some cases where the call is routed around we get a "correction" for the calling number after the call is setup. Could be something like that going on.
Either way, it's probably not random - the first thing to check is the calling number that's in the subject - does it match a subscriber's extension? If not then you need to look at why that calling number was provided to us or you can add that calling number as an alternate extension for the subscriber in question and messages from this phone will be tagged as sub to sub messages.
