The "LEGO" games: LEGO: Batman, LEGO Starwars etc. Make you think by putting puzzles together or destroying objects to get hints. The Devidian space station mission had this idea, but what about combining it with combat sections and/or defeating certain characters to get need pieces/info?
I agree (me agreeing with Valias, somebody call 911!) that would make things a lot more interesting. Rather than doing just environmental-based ones (the two Breen Series puzzles come to mind), actually having to destroy objects and stuff would be a fun way. Also, it would be fun if we had to use them a certain way.
Anyways, yeah, that's about as good as you can get with puzzles when it comes to MMO games. It's not on the Star Trek television episode level of mysterious and mind boggling, but you gotta understand the limitations of an MMO. They gotta be combat heavy. I don't envy Cryptic's job on making more diplomatic or puzzle based missions.
...Actually I do.
If we're going to get more complex mind bending puzzles and problems, Cryptc will have to do something extraordinary and bold. Turn riddles into missions.