The paid flag by default is part of the query string, which is part of the URL. As long as that paid query string parameter makes it to your landing page, you should be good.
A common wrecker of query string parameters are redirects. Can you confirm you don't have any on any of your paid search landing pages? Also, can you provide a paid search term where your site appears in results that we can click on and test?