Are you still connected to the Internet when you paste the graphic into an
Outlook message?

Yes, I am always connected to Internet.

If you press Alt+F9 in Word, what do you see where the
graphic is located?

It could be anything. For example, these two cases:

{INCLUDEPICTURE
"http://netgsel.safaribooksonline.com/portals/netgsel/images/banner.jpg" \*
MERGEFORMATINET }

{HYPERLINK "http://netgsel.safaribooksonline.com/." \o "Safari Enterprise
Library home page" }

NB. Just because those are links, it doesn't mean this was all the clipboard
had. It is Word who decided to paste data this way.