I've never used either of them, so cant help much.
I assume you removed the shortcuts from \Startup, then reset, then tried to uninstall - that looks like what you said and should be correct.
What I'd suggest is that you rename (do NOT delete) the \Program Files folders for these apps, and see what effect it has. Send yourself some messages - you might get error messages, but can you still see your messages in the built-in Messaging app?
If you can still get to the messages you sent to yourself then it's probably safe to delete the \Program Files folders for those apps (they'll still appear in the Remove Programs list though).
The other option is to contact the developers themselves, they might have better advice