Yes, however I believe that an unpredictable set must satisfy two criteria.
1. The benefits of using the unorthodox set must outweigh the benefits of using a more standard set. Choice Specs Gyarados is unpredictable, and may score a surprise kill, but it is overall inferior to the standard physical Gyarados.
2. The set must be useful even after the surprise is ruined. This mostly applies to shoddy as you will often face the same opponent more than once in a laddering session. Yes, that Choice Band Blissey nabs a surprise kill, but in all future battles against the same opponent it is useless, if not a liability.
The two go hand in hand pretty much since usually if the set fails to meet the 2nd criteria it also fails to meet the 1st and vice versa.
This is a pretty good set of rules.
One of the most amazing things I've seen is when Donut (IIRC) first started using SubRev Yanma. It was just a very clever moveset. In DP the more common set is Specs Yanmega so running the SubRev set can often work well, and instead of getting killed by SR he can use it to setup quicker. Look at Garchomp, Draco Meteor was considered useless until someone (forgot who, sorry) thought about it a bit and came up with the most devastating set since Bellyzard in 200.
One tip in remaining unpredictable is to run variants. Sometimes I'd run CM and sometimes Counter, so when rebattled someone they would only think they know what I had.
In ADV I used to have Metagross problems so I'd bring in Slowbro. I ran Rest, Surf, CM/Counter (the two variants) and Fire Blast. Fire Blast/Counter turned out to be very useful, and often crippled opponents expecting a Ice Beam/Psychic.
Similarly back then all Venusaur were Physical, Razor Leaf/Hidden Power were its best special attacks. That said it did have the terrible Frenzy Plant, yet it often secured crucial KOs and after some testing I found that this rarely resulted in something setting up for a sweep. Considering Venusaur typically only ran less than a dozen moves most people expected some kind of status/physical build, my crazy set often worked. Yet at the same time it could shut down counters reducing the risk. One of the things about testing sets like this is that you should expect to lose a lot during the testing and tweaking process. I probably wouldn't use it in a tourney, but it was fun and worked more often than not.
Deviating from the standard applies to EVs too. Investing in defenses can often stop counters thinking they have a guaranteed OHKO dead in their tracks. Look at the BulkyGyara spread to see how dangerous a well thought out EV allocation can be.
Uncertainty can be very unsettling, any Pokemon that can run a number of sets is inherently threatening because you don't know what its going to do. A Pokemon that is known for Subpunching isn't going to attract a Blissey switchin, but one that usually CMs can suprise Blissey with a Focus Punch for a 2HKO, forcing it out while still remaining safe behind a sub with two spare moves to use the CM.
Also occasionally you'll run into a Pokemon that you don't know a lot about, that can be pretty unsettling too.
For example, you have your Skarmory out against an Infernape, and he knows you have a Heatran waiting in the wings. He selects Close Combat to destroy the obvious Heatran switchin, so you use Brave Bird and OHKO Infernape while taking a small amount of damage.
That is outpredicting rather than being unpredictable. If your move choice relies on info about their team they may predict your move based on that knowledge.
For example say Ice Beam does 40% and Thunderbolt does 80%, and they know you have neither move. In this situation you can often use either move randomly as Ice Beam + TB is a KO, and it prevents your opponent from learning a pattern so they can safely switch into a predicted move. If you IB they will maybe think you don't have TB and get killed, if you IB and they switch expecting TB you probably hit for at least neutral damage if not SE. Boltbeam isn't just good for coverage, but because it allows you to play mind games while usually hitting at least neutral.
Same principle applies to Pokemon that run/can run mixed sets. Your opponent has a tougher time knowing what to switch in to take the attack. Its why things like Salamence are so devastating.
Prediction is a two way street, they more you try to predict the more predictable you become.