Appreciate I'm a bit late to the party but for anyone looking for high altitude GPS modules current information is as follows. Currently there are four GPS modules known to work at high altitudes ( >18km) they use an AND statement rather than an OR statement for their adhereance to the the COCOM limits. These have been launched by members of the high altitude balloon community.
Known Problem GPS Modules :
Also please note the following : Cheap keyring cameras i.e AEE MDS91S etc will act as very effective GPS jammers in close proximity to your GPS Chip.
Although we are advised the MediaTek MT3339 GPS modules are meant to work at high altitude the one launch done with one topped out at 10km (GlobalTop GPS-FGPMMOPA6C). This may have been a configuration error we don't have full information on these modules at this time.
Hope this helps to anyone looking for high altitude capable GPS modules. If you need further information there is a wealth of coding examples and advice over at the UKHAS Website.
This is even later, but I just wanted to add a quick comment about the Venus 634FLPx. I've personally flown this unit to 63k feet and can verify that it worked without problems. This is a version of the board that Sparkfun sells that is at least 2 years old, so pretty much any 634/638 board should work without issue.
For more data points, see the Trackuino project which was built using the Venus 634FLPx.
From what Skytraq (the manufacturer's of the Venus 634FLPx) has told me, the SUP500F/R and the S1315F should also work > 10km (I haven't verified this yet).
Just to provide an additional data point.
PS Did you look at the MTK3339 datasheets? It seems to get high altitude support it appears you'll need to use some non-standard binary mode (not NMEA183) called One Sentence for this to work. I had high hopes for this unit but anymore I'm not so sure.