Would it be possible to use http://www.nkcelectronics.com/bluetooth-module-serial-port.html in order to establish a bluetooth connection between my Mobile (win mobile.. that side is not a problem) and an arduino connected to that module? I would like to build myself a GPS module that i can connect with my phone over bluetooth, and that seemed to be the best cost efficient module..
Short answer: absolutely yes.
And the slave device is also right choice in this case (because you want to initiate the connection from your mobile phone). If I remember right the latest Win CE os does not even support being the slave device.
For more information about master-slave thing:
http://discussion.forum.nokia.com/forum/archive/index.php/t-52745.html
Oh and just for the safety reasons regarding your homemade-gps project:
If you are in a hurry jump to [1:39]
Sure you can get the arduino to connect to the mobile phone but you will need to develop software that can receive the data and put it to use as you want. right?