So up until now I've been unable to see the paid apps in the Android Market.

I don't know whether I actually want to buy any yet.. as the free ones are pretty comprehensive, but it'd be nice to at least see them!
As I'm on Virgin in Australia and they're not likely to get Android Market support in the next century I found another way around it and discovered market-enabler.

http://code.google.com/p/market-enabler/

This little app (I tried the beta) - lets you see what your provider id's are and you can fake another provider if you want.
I don't know any of the 3/Vodafone provider tags, so I just used T-Mobile for now and this works pretty sweet for me.