What is your print bed surface made off?

Normally I use a metal scrapper with a very thin edge to wedge to ply the part out, you just have to be careful not to scratch the print bed surface.
Also when I do my own designs, if I see the part could have sticking problems, I add printing pads around the bottom edges, basically circular pads about 0.5 or 0.6mm high that are easy to get a wedge under and then they help to lift the whole part off.
Simply adding a skirt around also helps to do that, but if the part is stuck good and hard the skirt will probably shear around the bottom edge without ever lifting the part; I suppose it would be possible to use a skirt more than one layer in height, two or three, to help with that.

Some time ago in the Slic3r subforum at the reprap forums I suggested an idea to have the option to create a pull-up tab when doing a skirt, like this:

PullUpTab.jpg

The red represents the part being printed and the black the skirt plus the tab and ring to pull it off the print bed. It could be easy to create that as part of the stl too, but of course having it as an option in the slicing software would be more convenient.

I forgot to add, if your part is really stuck you may have to remove the print bed and give it a tap or two on the underside with a rubber hammer or something similar; depending on what your print bed is made of and how it is installed this method could go from being very easy and quick to a risky PITA... and all the stages in between.