Opening a new Terminal window when it's running on another desktop
By Golly, I think I've found it this time.

Fire up Utilities/AppleScript Editor. Copy/paste the lines below. Save it and add it to your Dock. Whenever you click it you'll get a new window on your current desktop. You need to have "Enable support for assistive devices" activated in System Preferences - Universal Access. 

tell application "Terminal" to activate
tell application "System Events"
    tell process "Terminal"
        click menu item "New Window" of menu "Shell" of menu bar 1
    end tell
end tell


Source: adapted from this hint regarding Safari.