There's quite a few ways to verify past salary. Specially some employers report employment information to private databases and your potential employer runs a "employment report," like banks run a credit report, as part of a mandatory background check. To see if you lied.
Of course, they can't do that without your permission but agreeing to a background check is a condition of employment.
The database i am thinking of is, IIRC, owned by Lexis Nexis and they claim to have employment data for the majority of Fortune 500 companies.
EDIT: The database I am thinking of is called The Work Number and is owned by Equifax.
http://www.businessinsider.com/salary-information-not-privat...
>One woman interviewed by CNBC had a Work Number report that was a whopping 22 pages long, complete with a copy of all of her paychecks over the years.
They claim to have employment information for over 1/3rd of American adults.