I use an Android; it has copy-and-paste. I believe I have used it exactly once in over a year of using the phone - I had started composing an SMS to the wrong person and decided to copy/paste the text instead of simply typing it again.
For most users, I am guessing the most common use case is copying a browser link to an email/IM/SMS, and this can be supported without an actual copy/paste implementation. The hard part of full-blown copy/paste isn't implementing copy/paste storage, it is figuring out the UI for selecting text on a touch screen.
you couldn't just change the addressee? well, that sucks. my "horrible" winmo 6.1 device lets' me do that, and it auto-completes based on my contact list.
but yes, copy+paste isn't all that necessary, but i can imagine mobile bloggers, among others, needing it from time to time.
btw, don't downvote me for using winmo. i'm not a fanboy, I just get tethering (bluetooth/usb), opera mini (the latest version is great), skyfire (streams flash/sivlerlight). It's a bit slow and the ui isn't great but I use a utily that helps me start apps using keyboard shortcuts and can multi-task (go figure) very easily.
My iPhone got undo/cut/copy/paste in the OS 3.0 update. The main difference in my life is when I carry my phone in my hand without locking it, swaying my arm back and forth triggers the "shake to undo" gesture, and the phone complains "nothing to undo".
For most users, I am guessing the most common use case is copying a browser link to an email/IM/SMS, and this can be supported without an actual copy/paste implementation. The hard part of full-blown copy/paste isn't implementing copy/paste storage, it is figuring out the UI for selecting text on a touch screen.